كيف واحد-طريقة تجزئة مهام العمل ؟ (تحريرها)

Question

قرأت مقالة ويكيبيديا عن التجزئة md5 ولكن ما زلت لا أستطيع أن أفهم كيف تجزئة لا يمكن أن يكون "المعاد" العودة إلى النص الأصلي.

هلا شرح لي أحدكم إلى شخص يعرف القليل جدا عن التشفير كيف يعمل هذا ؟ ما هو جزء من وظيفة يجعل من واحد ؟

Answer 1

نظرًا لأن الجميع حتى الآن حددوا ببساطة ما هي وظيفة التجزئة ، سأعض.

وظيفة اتجاه واحد ليست مجرد وظيفة تجزئة-وظيفة تفقد المعلومات-ولكن وظيفة f التي ، أعطيت صورة y ("SE" أو 294 في الإجابات الموجودة) ، من الصعب العثور f(x)=y.

هذا هو السبب في أنهم يطلق عليهم في اتجاه واحد: يمكنك حساب صورة ولكن لا يمكنك العثور على صورة مسبقة لصورة معينة.

لا يوجد أي من وظيفة التجزئة العادية المقترحة حتى الآن في الإجابات الموجودة لديها هذه الخاصية. لا أحد منهم هو وظائف تجزئة تشفير في اتجاه واحد. على سبيل المثال ، بالنظر إلى "SE" ، يمكنك بسهولة التقاط الإدخال "SXXXE" ، وهو إدخال مع الخاصية التي يتمتع بها X-Encode ("SXXXE") = SE.

لا توجد وظائف "بسيطة" في اتجاه واحد. يجب عليهم خلط مدخلاتهم بشكل جيد بحيث لا تتعرف فقط على المدخلات على الإطلاق في الإخراج ، لكن أنت لا تتعرف على مدخلات أخرى أيضًا.

اعتادت SHA-1 و MD5 أن تكون وظائف ذات اتجاه واحد شائع ، لكنهما كلاهما مكسور تقريبًا (يعرف أخصائي كيفية إنشاء صور مسبقة للصور المعطاة ، أو يمكنهم تقريبًا القيام بذلك). هناك مسابقة جارية لاختيار مسابقة قياسية جديدة ، والتي سيتم تسميتها SHA-3.

تتمثل الطريقة الواضحة في عكس وظيفة في اتجاه واحد في حساب العديد من الصور والحفاظ عليها في جدول مرتبط بكل صورة ما قبل الصورة التي أنتجتها. لجعل ذلك مستحيلًا في الممارسة العملية ، تحتوي جميع الوظائف أحادية الاتجاه على ناتج كبير ، على الأقل 64 بت ولكن ربما أكبر بكثير (على سبيل المثال ، 512 بت).

تحرير: كيف تعمل معظم وظائف تجزئة التشفير؟

عادة ما يكون لديهم في جوهر وظيفة واحدة تقوم بتحولات معقدة على كتلة من البتات (أ كتلة الشفرة). يجب أن تكون الوظيفة تقريبًا (لا ينبغي أن تقوم بتخطيط الكثير من التسلسلات إلى نفس الصورة ، لأن ذلك قد يسبب نقاط الضعف في وقت لاحق) ولكن لا يجب أن يكون تحريفًا تمامًا. وهذه الوظيفة يتم تكرار عدد محدد من المرات ، وهو ما يكفي لجعل الإدخال (أو أي إدخال محتمل) مستحيل التعرف عليه.

أخذ مثال skein, ، أحد المرشحين الأقوياء لسياق SHA-3. يتم تكرار وظيفتها الأساسية 72 مرة. العدد الوحيد من التكرارات التي يعرفها المبدعون في الوظيفة كيفية ربط المخرجات في بعض الأحيان ببعض المدخلات هو 25. يقولون إن لديها "عامل أمان" 2.9.

Answer 2

فكر في تجزئة أساسية حقًا - بالنسبة لسلسلة الإدخال ، قم بإرجاع مجموع قيم ASCII لكل حرف.

hash( 'abc' ) = ascii('a')+ascii('b')+ascii('c')
              = 97 + 98 + 99
              = 294

الآن ، بالنظر إلى قيمة التجزئة البالغة 294 ، هل يمكنك معرفة ما هي السلسلة الأصلية؟ من الواضح لا ، لأن "ABC" و "CBA" (وعدد لا يحصى من الآخرين) يعطيان نفس قيمة التجزئة.

تعمل وظائف تجزئة التشفير بنفس الطريقة ، باستثناء أنه من الواضح أن الخوارزمية أكثر تعقيدًا. ستكون هناك دائمًا تصادمات ، ولكن إذا كنت تعرف سلسلة s تجزئة ل h, ، بعد ذلك ، يجب أن يكون الأمر صعبًا للغاية ("غير ممكن حسابيًا") بناء سلسلة أخرى تجزئة أيضا h.

Answer 3

إطلاق النار على تشبيه بسيط هنا بدلاً من تفسير معقد.

بادئ ذي بدء ، لنقسم الموضوع إلى جزأين ، عمليات في اتجاه واحد وتجزئة. ما هي العملية في اتجاه واحد ولماذا تريد واحدة؟

تسمى عمليات إحدى الطرق لأنها غير قابلة للعكس. يمكن عكس معظم العمليات النموذجية مثل الإضافة والضرب بينما لا يمكن عكس قسم Modulo. لماذا هذا مهم؟ نظرًا لأنك ترغب في توفير قيمة الإخراج التي يصعب تكرارها بدون المدخلات الأصلية و 2) لا توفر طريقة لمعرفة المدخلات من الإخراج.

تفريغ

إضافة:

4 + 3 = 7  

يمكن عكس ذلك عن طريق أخذ المبلغ وطرح أحد الإضافات

7 - 3 = 4  

عمليه الضرب:

4 * 5 = 20  

يمكن عكس ذلك عن طريق أخذ المنتج وتقسيمه على أحد العوامل

20 / 4 = 5

لا يمكن عكسه

قسم Modulo:

22 % 7 = 1  

لا يمكن عكس ذلك لأنه لا توجد عملية يمكنك القيام بها إلى الحاصل وتوزيعات الأرباح لإعادة تشكيل المقسوم (أو العكس).

هل يمكنك العثور على عملية لملء أين "؟" هو؟

1  ?  7 = 22  
1  ?  22 = 7

مع ما يقال ، فإن وظائف التجزئة أحادية الاتجاه لها نفس الجودة الرياضية مثل قسم Modulo.

لماذا هذا مهم؟

دعنا نقول إنني أعطيتك مفتاحًا لخزانة في محطة الحافلات التي تحتوي على ألف خزانة وطلبت منك تسليمها إلى مصرفي. كونك الرجل الذكي الذي أنت عليه ، ناهيك عن المشبوهة ، ستنظر فورًا على مفتاح معرفة رقم الخزانة المكتوب على المفتاح. مع العلم بذلك ، لقد فعلت بعض الأشياء الملتوية ؛ أولاً ، وجدت رقمين عند تقسيمهم باستخدام قسم Modulo يعطيني رقمًا في النطاق بين 1 و 1000 ، ثانيًا ، قمت بمسح الرقم الأصلي وكتبت عليه المقسوم من زوج الأرقام ، واخترت ثانيًا محطة حافلة تحتوي على أ حراسة حماية الخزائن من الأوغاد من خلال السماح للأشخاص فقط بتجربة خزانة واحدة في اليوم مع مفتاحهم ، والثالث يعرف المصرفي توزيعات الأرباح بالفعل ، لذلك عندما يحصل على المفتاح ، يمكنه القيام بالرياضيات ومعرفة الخزانة التي سيتم فتحها.

إذا اخترت المعاملات بحكمة ، فيمكنني الاقتراب من علاقة فردية بين الحاصل وتوزيعات الأرباح التي تجبرك على تجربة كل خزانة لأن الإجابة تنشر نتائج المدخلات المحتملة على نطاق الأرقام المطلوبة ، الخزائن متوفر في المحطة. في الأساس ، هذا يعني أنه لا يمكنك اكتساب أي معرفة بالباقي حتى لو كنت تعرف أحد المعاملات.

لذا ، الآن يمكنني "الوثوق" بتوصيل مفتاح مالكها الشرعي دون القلق من أنه يمكنك بسهولة تخمين الخزانة التي ينتمي إليها. من المؤكد أنه يمكنك الغاشمة في البحث عن جميع الخزائن ، لكن ذلك سيستغرق ما يقرب من 3 سنوات ، الكثير من الوقت لاستخدام المصرفي الخاص بي لاستخدام المفتاح وتفريغ الخزانة.

انظر الإجابات الأخرى لمزيد من التفاصيل حول وظائف التجزئة المختلفة.

Answer 4

إليك مثال بسيط للغاية. افترض أنني بداية تشفير وأقوم بإنشاء وظيفة تجزئة تقوم بما يلي:

int SimpleHash(file) {
    return 0 if file.length is even;
    return 1 if file.length is odd;
}

الآن ها هو الاختبار. SimpleHash(specialFile) هو 0. ما هو ملفي الأصلي؟

من الواضح أنه لا توجد طريقة لمعرفة (على الرغم من أنه من المحتمل أن تكتشف بسهولة أن تجزئة بلدي يعتمد على طول الملف). لا توجد وسيلة "إعادة تشكيل" ملفي بناءً على التجزئة لأن التجزئة لا تحتوي على كل ما فعله ملفي.

Answer 5

التجزئة هي (جدا) تشفير.

لإعطائك مثالًا أبسط ، تخيل ترميزًا وهميًا من أحرف لكلمة من 5 أحرف تسمى "X-Encoding". خوارزمية الترميز X بسيط: خذ الأحرف الأولى والأخيرة من الكلمة.

لذا،

X-encode( SAUCE ) = SE
X-encode( BLOCK ) = BK

من الواضح أنه لا يمكنك إعادة بناء الصلصة من SE الترميز (على افتراض أن مجموعتنا من المدخلات المحتملة هي كل الكلمات ذات 5 أحرف). يمكن أن تكون الكلمة بسهولة الفضاء.

جانبا ، تسمى حقيقة أن الصلصة والفضاء تنتج SE كترميز الاصطدام, ، ويمكنك أن ترى أن X-ecoding لن يصنع تجزئة جيدة جدًا. قون

Answer 6

بعبارات بسيطة, وظيفة تجزئة يعمل عن طريق جعل كبير فوضى متشابكة من إدخال البيانات.

انظر MD5 على سبيل المثال.يقوم بمعالجة البيانات المدخلة من قبل 512 بت كتل.كل كتلة تنقسم إلى 16 32 بت الكلمات.هناك 64 الخطوات كل خطوة باستخدام واحدة من 16 إدخال الكلمات.لذلك كل كلمة تستخدم أربع مرات خلال الخوارزمية.هذا هو المكان واحد wayness يأتي من:أي إدخال بت الإدخال في عدة أماكن بين اثنين من هذه المدخلات وظيفة يمزج جميع البيانات الحالية معا بحيث كل المدخلات بعض الآثار أكثر من 128 بت إدارة الدولة.وهذا يمنعك من عكس وظيفة ، أو الحوسبة الاصطدام ، من خلال النظر في جزء فقط من البيانات.يجب أن ننظر في كل 128 بت و مساحة 128 بت كتل واسعة جدا أن تكون بكفاءة سار.

الآن MD5 لا القيام بعمل جيد في ذلك ، منذ التصادم على أن وظيفة يمكن العثور عليها.من مبرمجة وجهة نظر ، MD5 هو استدارة وظيفة التشفير.تجهيز رسالة واحدة كتلة M (512 بت) يستخدم مدخلا الدولة V (128-بت) ، يحسب الدولة الجديدة V V' = V + E(M, V) حيث '+' هي كلمة الحكمة ذلك ، و 'ه' يحدث أن تكون التشفير المتناظر وظيفة (الملقب 'block cipher) الذي يستخدم M مفتاح V الرسالة المشفرة.من نظرة فاحصة ، E هو نوع من "تمديد Feistel الشبكة" ، على غرار قصر كتلة الشيفرة مع أربعة أرباع بدلا من نصفين.التفاصيل ليست مهمة هنا ، وجهة نظري أن ما يجعل "جيد" تجزئة وظيفة من بين وظائف التجزئة التي تستخدم هذا الهيكل (يسمى "ميركيل-Damgård") ، على غرار ما يجعل كتلة الشفرات "آمنة".النجاح في تصادم الهجمات على MD5 استخدام تفاضلية تحليل الشفرات ، أداة التي تم الهجوم كتلة الأصفار في المقام الأول.

من كتلة جيدة الشفرات إلى وظيفة تجزئة جيدة, هناك خطوة لا يمكن استبعاده.مع ميركيل-Damgård هيكل تجزئة وظيفة آمنة إذا الأساسية كتلة التشفير هو مقاومة "الرئيسية ذات الصلة الهجمات" ، غامض نوعا ما الممتلكات ضد أي كتلة الأصفار نادرا ما عزز لأن التشفير المتناظر, الرئيسية ذات الصلة الهجمات بالكاد أي أثر عملي.على سبيل المثال, AES التشفير اتضح أن لا تكون مقاومة الرئيسية ذات الصلة الهجمات كما تمنى ، وهذا لا تثير الذعر العام.أن المقاومة ليست جزءا من الخصائص التي سعت عندما AES صمم.فقط يمنع تحول AES في وظيفة تجزئة.هناك وظيفة تجزئة يسمى ويرلبول الذي يبني على مقتبسة من ريجنديل, "ريجنديل" كونها الأولى اسم ما أصبح AES;ولكن دوامة تأخذ الرعاية لتعديل أجزاء من ريجنديل التي هي ضعيفة الرئيسية ذات الصلة الهجمات.

وهناك أيضا غيرها من الهياكل التي يمكن أن تستخدم لبناء تجزئة الوظيفة.المعيار الحالي الوظائف (MD5, SHA-1, و "SHA-2" الأسرة الملقب SHA-224, SHA-256, SHA-384 و SHA-512) ميركيل-Damgård الوظائف ، ولكن العديد من أن يكون خلفاء لا.هناك المنافسة الجارية ، التي نظمتها نيست (الولايات المتحدة الاتحادية المنظمة التي تتعامل مع هذا النوع من الأشياء) ، لتحديد معايير جديدة وظيفة تجزئة ، يطلق عليها اسم "SHA-3".انظر هذه الصفحة للحصول على التفاصيل.الآن هم أسفل إلى 14 مرشحا من أولي 51 (لا عد اثني عشر الإضافية التي فشلت الإدارية اختبار إرسال الخضوع التام مع الرمز الذي يجمع ويعمل بشكل صحيح).

دعونا الآن أكثر المفاهيم نظرة.تأمين وظيفة تجزئة ينبغي أن تبدو وكأنها عشوائية أوراكل:oracle هو الصندوق الأسود الذي عندما تعطى رسالة م كما المدخلات والمخرجات إجابة h(M) والذي يتم اختياره عشوائيا ، موحد ، في الإخراج الفضاء (أيكل nبت السلاسل إذا كانت وظيفة تجزئة إخراج طول n).إذا أعطيت نفس الرسالة م مرة أخرى كإدخال, oracle النواتج نفس القيمة من ذي قبل.وبصرف النظر عن هذا التقييد ، إخراج أوراكل على غير المستخدمة سابقا الإدخال م لا يمكن التنبؤ بها.يمكن للمرء أن يتصور أوراكل كما حاوية غنوم الذي يلقي النرد ، بعناية سجلات الإدخال رسائل المقابلة النواتج في كتاب كبير ، لدرجة أنه شرف له أوراكل العقد.لا توجد وسيلة للتنبؤ بما القادم سوف يكون الإخراج منذ جنوم نفسه لا يعرف ذلك.

إذا عشوائي أوراكل موجودا ، ثم عكس وظيفة تجزئة كلف 2^n:من أجل أن يكون ناتج معين ، ليس هناك استراتيجية أفضل من استخدام متميزة إدخال الرسائل حتى واحد ينتج القيمة المتوقعة.بسبب موحدة اختيار عشوائي, احتمال النجاح هو 1/(2^n) في كل محاولة ، ومتوسط عدد طلبات النرد رمي جنوم سوف يكون 2^n.عن التصادم (العثور على اثنين متميزة المدخلات التي ينتج نفس قيمة التجزئة), التكلفة حوالي *1.4*2^(ن/2)* (تحدث تقريبا ، مع *1.4*2^(ن/2)* النواتج يمكننا تجميع حوالي 2^n أزواج من إخراج كل وجود احتمال 1/(2^n) مطابقة ، أيوجود اثنين متميزة المدخلات التي لها نفس الناتج).هذه هي أفضل ما يمكن القيام به مع عشوائي أوراكل.

ولذلك نحن نبحث عن وظائف التجزئة التي هي جيدة مثل عشوائي أوراكل:يجب أن تخلط إدخال البيانات في مثل هذه الطريقة التي لا نجد تصادم أكثر كفاءة من ما هي تكلفة ببساطة استدعاء الدالة 2^(ن/2) مرات.لعنة دالة البعثرة هي بنية رياضية ، أياختصارات والتي تسمح للمهاجم لعرض وظيفة تجزئة الدولة الداخلي (الذي هو كبير ، على الأقل n بت) كما الاختلاف على الرياضي الكائن الذي يعيش في أقصر بكثير الفضاء.30 عاما من البحوث العامة في التشفير المتناظر نظم أنتجت مجموعة كاملة من المفاهيم والأدوات (نشر سيل ، الفروق ، الخطي...) التي يمكن تطبيقها.أسفل الخط ، مع ذلك ، هو أنه ليس لدينا أي دليل على أن عشوائي أوراكل قد تكون موجودة في الواقع.نحن تريد دالة البعثرة التي لا يمكن مهاجمتها.ما لديك هي وظيفة تجزئة المرشحين ، أي هجوم حاليا المعروف, و أفضل نوعا ما, لدينا بعض الوظائف التي بعض أنواع الهجوم يمكن أن يكون ثبت عدم العمل.

لا يزال هناك بعض الأبحاث إلى أن يتم ذلك.

Answer 7

مجموعة مصفوفة
مع بعض التحديق ، تبدو المصفوفات الترابطية تشبه إلى حد كبير التجزئة. كانت الاختلافات الرئيسية هي عدم وجود رمز ٪ على أسماء التجزئة ، ويمكن للمرء فقط تعيين مفتاح واحد في كل مرة. وهكذا ، يمكن للمرء أن يقول $foo{'key'} = 1;, ، لكن فقط @keys = keys(foo);. وظائف مألوفة مثل كل منها ، والمفاتيح ، والقيم التي عملت كما تفعل الآن (وتم إضافة حذف في بيرل 2).

كان لدى Perl 3 ثلاثة أنواع من البيانات الكاملة: كان لديه رمز ٪ على أسماء التجزئة ، وسمح بتعيين تجزئة بأكملها في الحال ، وإضافة DBMopen (تم إهمالها الآن لصالح التعادل). استخدمت Perl 4 مفاتيح تجزئة مفصولة بفاصلة لمحاكاة المصفوفات متعددة الأبعاد (والتي يتم التعامل معها الآن بشكل أفضل مع مراجع الصفيف).

اتخذ بيرل 5 قفزة العملاقة للإشارة إلى المصفوفات الترابطية كتجزئة. (على حد علمي ، إنها اللغة الأولى التي تشير إلى بنية البيانات وبالتالي ، بدلاً من "جدول التجزئة" أو شيء مشابه.) ومن المفارقات إلى حد ما ، كما نقلت الكود ذي الصلة من hash.c إلى HV.C.

التسميات
القواميس ، كما هو موضح سابقًا ، هي مجموعات غير مرتبة من القيم المفهرسة بواسطة مفاتيح فريدة. يطلق عليهم في بعض الأحيان المصفوفات الترابطية أو الخرائط. يمكن تنفيذها بعدة طرق ، أحدها باستخدام بنية بيانات تُعرف باسم جدول التجزئة (وهذا ما يشير إليه Perl باعتباره تجزئة).

إن استخدام Perl لمصطلح "التجزئة" هو مصدر بعض الالتباس المحتمل ، لأن إخراج وظيفة التجزئة يسمى أحيانًا تجزئة (خاصة في سياقات التشفير) ، ولأن جداول التجزئة لا تسمى عادة التجزئة في أي مكان آخر.

لكي تكون على الجانب الآمن ، راجع بنية البيانات كجدول التجزئة ، واستخدم مصطلح "التجزئة" فقط في سياقات واضحة محددة.