تشفير Rsa. مثال على خوارزمية تشفير rsa. EDS والمفتاح العمومي

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

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

خوارزمية RSA

تشفير المفتاح العام

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

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

برنامج تجريبي يعتمد على خوارزمية RSA

مخطط Rivest-Shamir-Adleman (RSA) هو حاليًا مخطط تشفير المفتاح العام الوحيد المقبول على نطاق واسع في الممارسة العملية.

مخطط RSA هو كتلة تشفير يكون فيها كل من النص العادي والنص المشفر أعدادًا صحيحة بين 0 و ص- 1 بالنسبة للبعض ص.

يتم تشفير النص العادي في كتل ، يحتوي كل منها على قيمة ثنائية أقل من بعض الأرقام المحددة ص.وهذا يعني أن طول الكتلة يجب ألا يتجاوز log2 ("). في الممارسة العملية ، يتم اختيار طول الكتلة على قدم المساواة 2 كبت أين 2k يعتمد المخطط الذي طوره Rivest و Shamir و Adleman على تعبيرات القوة. يمكن تمثيل التشفير وفك التشفير لكتلة النص العادي M وكتلة النص المشفر C بالصيغ التالية:

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

لاستخدام هذه الخوارزمية لتشفير المفتاح العام ، يجب استيفاء المتطلبات التالية:

يجب أن تكون هناك قيم ه ، دو فماذا او ما م إد =م (تعديل ع)لجميع م ن.

يجب أن يكون من السهل نسبيًا حساب IVT و من c1لجميع قيم M p.

يجب أن يكون من المستحيل تقريبًا تحديده دمتوفرة لها ص.

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

هنا ، النتيجة الطبيعية من نظرية أويلر مناسبة تمامًا: لأي عددين أوليين من هذا القبيل صو فومثل أي عددين صحيحين بيت ،ماذا او ما n = pqn0 وعدد صحيح عشوائي لالعلاقات التالية تحمل:

حيث φ (ن) هي دالة أويلر التي تساوي قيمتها عدد الأعداد الصحيحة الموجبة الأصغر من صوالجريمة المشتركة مع ص.

في حالة بسيطة صو فلدينا f (ص) - (ص - 1 ) (ف -واحد). لذلك ، يتم الحصول على النسبة المطلوبة بشرط

هذا يعادل العلاقات التالية:

أولئك. قطيعهي نموذج معكوس متبادل φ (ن). لاحظ أنه وفقًا لقواعد الحساب في فئات البقايا ، يمكن أن يكون هذا هو الحال فقط عندما د(وبالتالي ه)هي جريمة مشتركة مع φ (ش). في التدوين المكافئ (f (/ 7) ، د) =.

الآن لدينا كل شيء لتمثيل مخطط RSA. مكونات الدائرة هي:

صو ف- عددان أوليان (سري ، مختار) ؛

ف pq(مفتوح ، محسوب) ؛

مثل ه، هذا (و (ط) ، ه)= 1.1 هـ

د = ه ل(mod f (/؟)) (سرية ، محسوبة).

يتكون المفتاح الخاص من (د ، ن) ،وفتح من (ه ، ع).لنفترض أن المستخدم "أ" قد نشر مفتاحه العام ، وسيقوم المستخدم "ب" الآن بإرسال رسالة "م" إليه.

ثم يحسب المستخدم B الرسالة المشفرة

بعد تلقي هذا النص المشفر ، يقوم المستخدم A بفك تشفيره عن طريق الحساب

من المنطقي أن نعطي هنا الأساس المنطقي لهذه الخوارزمية. تم اختيارهم قطيعمثل ذلك

لذلك ، يبدو كك> (ن) +.ولكن نتيجة نظرية أويلر لأي عددين أوليين من هذا القبيل صو كيوأعداد صحيحة ن = pqnم أن تتحقق العلاقات

لهذا السبب

الآن لدينا

يلخص الجدول 10.1 خوارزمية RSA وفي الشكل. يوضح الشكل 10.1 مثالاً على تطبيقه. في هذا المثال ، يتم حساب المفاتيح على النحو التالي:

  • 1. يتم اختيار عددين أوليين: p-7 wq- 17.
  • 2. محسوبة ع = pq= 7 × 17 = 119.
  • 3. احسب f (ن) - (ص -) (ف - 1) = 96.
  • 4. اختيار ه، مع coprime φ (ع)= 96 وأقل من f (i) ؛ في هذه الحالة = 5.
  • 5. يتم تعريف هذا د،ماذا او ما دي= 1 (طراز 96) و د 96. القيمة المقابلة ستكون د = 77 ، لأن 77 × 5 = 385 = 4 × 96 + 1.
  • 6. والنتيجة هي مفتاح عمومي KU = (5 ، 119) ومفتاح خاص KR = (77 ، 119).

يوضح هذا المثال استخدام هذه المفاتيح مع إدخال نص عادي M = 19. بالنسبة للتشفير ، يتم رفع الرقم 19 إلى الأس الخامس ، مما ينتج عنه 2،476،099. ينتج عن القسمة على 119 ما تبقى من 66. لذلك ، 19119) ، وهكذا سيكون النص المشفر 66. بعد فك التشفير ، اتضح أن


أرز. 10.1.

الجدول 10.1

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

تاريخ الخلق

يأتي اسم RSA من الأحرف الأولى لأسماء Rivest و Shamir و Adleman ، وهم العلماء الذين وصفوا لأول مرة الألقاب علنًا في عام 1977. كليفورد كوكس ، عالم الرياضيات الإنجليزي الذي عمل في أجهزة المخابرات البريطانية ، طور لأول مرة نظامًا مكافئًا في عام 1973 ، لكن لم يتم رفع السرية عنه حتى عام 1997.

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

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

متى ظهر نظام التشفير بشكله الحديث؟

تُعزى فكرة نظام تشفير المفتاح غير المتماثل إلى Diffie و Hellman ، اللذين نشرا المفهوم في عام 1976 ، حيث قدموا التوقيعات الرقمية وحاولوا تطبيق نظرية الأعداد. تستخدم صياغتها سرًا مشتركًا تم إنشاؤه من الأس لبعض الوحدات النمطية لعدد أولي. ومع ذلك ، فقد تركوا مشكلة تنفيذ هذه الميزة مفتوحة ، حيث لم تكن مبادئ التخصيم مفهومة جيدًا في ذلك الوقت.

قام كل من Rivest و Adi Shamir و Adleman من MIT بعدة محاولات على مدار عام لإنشاء وظيفة أحادية الاتجاه يصعب فك تشفيرها. اقترح ريفيست وشامير (كعلماء كمبيوتر) العديد من الميزات المحتملة ، بينما بحث Adleman (كعالم رياضيات) عن "نقاط الضعف" في الخوارزمية. اتخذوا العديد من الأساليب وفي النهاية طوروا النظام النهائي في أبريل 1977 ، المعروف اليوم باسم RSA.

EDS والمفتاح العمومي

يعد التوقيع الرقمي الإلكتروني ، أو EDS ، جزءًا لا يتجزأ من المستندات الإلكترونية. يتم تشكيلها مع تغيير تشفير معين في البيانات. باستخدام هذه السمة ، من الممكن التحقق من سلامة المستند وسريته وأيضًا تحديد من يملكه. في الواقع ، هذا بديل للتوقيع القياسي المعتاد.

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

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

ما هو جوهر الخوارزمية؟

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

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

يتكون المفتاح العمومي من وحدة وأس عام. يتكون "خاص" من وحدة ومؤشر خاص ، يجب أن يظل سراً.

تشفير ملف RSA ونقاط الضعف

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

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

خوارزميات التشفير والحماية الإضافية

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

يعتمد أمان نظام التشفير RSA وتشفير المعلومات على مشكلتين رياضيتين: مشكلة تحليل الأعداد الكبيرة ومشكلة RSA نفسها. يعتبر الكشف الكامل عن النص المشفر والتوقيع الرقمي في RSA غير مقبول على افتراض أنه لا يمكن حل هاتين المشكلتين معًا.

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

التشغيل الآلي

يمكن استخدام أداة تسمى Yafu لتبسيط هذه العملية. الأتمتة في YAFU هي ميزة حديثة تجمع بين خوارزميات العوامل في منهجية ذكية وقابلة للتكيف تقلل من الوقت للعثور على عوامل أرقام الإدخال التعسفية. معظم تطبيقات الخوارزمية متعددة الخيوط ، مما يسمح لـ Yafu بالاستفادة الكاملة من التعددية أو المتعددة (بما في ذلك SNFS و SIQS و ECM). بادئ ذي بدء ، إنها أداة سطر أوامر مُدارة. يمكن تقليل الوقت المستغرق في البحث عن عامل تشفير باستخدام Yafu على جهاز كمبيوتر عادي إلى 103.1746 ثانية. تنتج الأداة معالجة بسعة 320 بت أو أكثر. إنه برنامج معقد للغاية يتطلب قدرًا معينًا من المهارات الفنية للتثبيت والتكوين. وبالتالي ، قد يكون تشفير RSA C ضعيفًا.

محاولات القرصنة في العصر الحديث

في عام 2009 ، عمل بنجامين مودي ، باستخدام مفتاح RSA-512 بت ، على فك تشفير النص المشفر لمدة 73 يومًا باستخدام برنامج مشهور فقط (GGNFS) وجهاز كمبيوتر مكتبي متوسط ​​(ثنائي النواة Athlon64 بسرعة 1900 ميجاهرتز). كما أظهرت هذه التجربة ، فقد استغرق الأمر أقل قليلاً من 5 غيغابايت من القرص وحوالي 2.5 غيغابايت من ذاكرة الوصول العشوائي لعملية "الغربلة".

اعتبارًا من عام 2010 ، كان أكبر رقم RSA مُصنَّف بطول 768 بت (232 رقمًا عشريًا ، أو RSA-768). استمر الكشف عنها لمدة عامين على عدة مئات من أجهزة الكمبيوتر في نفس الوقت.

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

آفاق

لذلك ، يُفترض عمومًا أن يكون RSA آمنًا إذا كانت الأرقام كبيرة بدرجة كافية. إذا كان الرقم الأساسي 300 بت أو أقل ، يمكن تحليل النص المشفر والتوقيع الرقمي في غضون ساعات قليلة على جهاز كمبيوتر شخصي باستخدام برنامج متاح بالفعل مجانًا. تم إثبات إمكانية اختراق مفاتيح 512 بت في وقت مبكر من عام 1999 باستخدام عدة مئات من أجهزة الكمبيوتر. في هذه الأيام ، يكون هذا ممكنًا في غضون أسابيع قليلة باستخدام الأجهزة المتاحة بشكل شائع. وبالتالي ، فمن المحتمل جدًا أن يتم كشف تشفير RSA على الأصابع بسهولة في المستقبل ، وسيصبح النظام قديمًا بشكل ميؤوس منه.

رسميًا في عام 2003 ، تم التشكيك في أمان مفاتيح 1024 بت. يوصى حاليًا بأن يكون طوله 2048 بت على الأقل.

RSAيستخدم نوعين من المفاتيح - e و d ، حيث e عام و d سرًا. افترض أن P هي النص العادي و C هي النص المشفر. تستخدم أليس C = P e mod n لإنشاء النص المشفر C من النص العادي P ؛ يستخدم Bob P = C d mod n لاستخراج النص المصدر (ملف) المقدم من Alice. يتم إنشاء عدد كبير جدًا من الوحدات n باستخدام عملية إنشاء المفاتيح ، والتي سنناقشها لاحقًا.

يتم استخدام الأس Modulo للتشفير وفك التشفير. كما ناقشنا بالفعل في المحاضرات 12-13 ، عند استخدام الخوارزمية السريعة ، فإن معامل الأسي ممكن في زمن كثير الحدود. ومع ذلك ، فإن إيجاد لوغاريتم معياري لا يقل صعوبة عن تحليل معامل العدد. لا توجد خوارزمية متعددة الحدود لذلك. هذا يعني أن أليس يمكنها تشفير الرسالة باستخدام المفتاح العام (هـ) في وقت متعدد الحدود. يستطيع بوب أيضًا فكها في زمن كثير الحدود (لأنه يعرف د). لكن لا تستطيع حواء فك شفرة هذه الرسالة لأنها ستضطر إلى حساب جذر الحرف e-th لـ C باستخدام الحساب النمطي. يوضح الشكل 14.5 الفكرة وراء RSA.


أرز. 14.5.

بمعنى آخر ، تستخدم أليس طريقة واحدة تعمل(نموذج الأس) مع ثغرة معروفة فقط لبوب. لا تعرف Eve الثغرة ، لذا لا يمكنها فك تشفير الرسالة. إذا وجد شخص ما خوارزمية متعددة الحدود لمعامل جذر e -th لـ n ، فلن يكون معامل الأسي n دالة أحادية الاتجاه.

إجراء

يوضح الشكل 14.6 الفكرة العامة للإجراء المستخدم في RSA.

يستخدم RSA وحدة الأس للتشفير / فك التشفير. من أجل مهاجمة النص الخاص ، يجب على حواء أن تحسب


أرز. 14.6.
هيكلان جبريان

يستخدم RSA بنيتين جبريتين: الحلقة والمجموعة.

حلقات التشفير / فك التشفير. يتم التشفير وفك التشفير باستخدام حلقة تبادلية بعمليتين حسابيتين: الجمع والضرب. في RSA ، هذه الحلقة عامة لأن modulo n عامة. يمكن لأي شخص إرسال رسالة إلى Bob باستخدام حلقة التشفير هذه.

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

يستخدم RSA بنيتين جبريتين: الحلقة المفتوحة R =< Z ن و + و x> والمجموعة السرية G =< Z (ن)* ، x>.

توليد المفتاح

يستخدم بوب الخطوات الموضحة في الخوارزمية 14.2 لإنشاء مفاتيحه العامة والخاصة. بعد إنشاء المفاتيح ، يعلن بوب أن المجموعة (e ، n) هي مفتاح الوصول العام الخاص به: يخزن بوب d كمفتاحه الخاص. يستطيع بوب رفض p و q و ؛ لا يمكنهم تغيير مفتاحه الخاص دون تغيير الوحدة النمطية. من أجل السلامة ، الحجم الموصى به لكل p أو q بسيط هو 512 بت (حوالي 154 رقمًا عشريًا). يحدد هذا حجم الوحدة ، n هي 1024 بت (309 رقمًا).

14.2. جيل مفتاح RSA

في RSA ، tuple (e، n) هو مفتاح وصول عام ؛ عدد صحيح د - مفتاح سري.

التشفير

يمكن لأي شخص إرسال رسالة إلى بوب باستخدام مفتاح الوصول العام الخاص به. يمكن إجراء التشفير في RSA باستخدام خوارزمية متعددة الحدود ، كما هو موضح في الخوارزمية 14.3. تمت مناقشة خوارزمية الأُس السريع في المحاضرات 12-13. يجب أن يكون حجم النص المصدر أقل من n ؛ إذا كان حجم النص الأصلي أكبر ، فيجب تقسيمه إلى كتل.

تحت القطع ، تم وصف أمثلة لاختيار معلمات تشفير RSA "سيئة".

"يجب التأكيد على أنه يجب توخي الحذر عند اختيار معامل RSA (أرقام ن) لكل مراسل للشبكة. في هذا الصدد ، يمكن قول ما يلي. يمكن للقارئ التحقق من ذلك بشكل مستقل ، مع العلم بإحدى الكميات الثلاث ص, فأو φ (ن)، يمكن للمرء أن يجد بسهولة المفتاح السري RSA ... ".

دعونا نضيف هذا النص. إذا كان اختيار وحدة تشفير RSA غير ناجح ، كما هو الحال في المثال التعليمي أدناه ، فمن الممكن فك تشفير النص دون وجود مفتاح سري ، أي دون معرفة أي من الكميات الثلاثة المسماة.

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

أولاً ، دعنا نعطي المثال نفسه من الصفحات 313-315 من الدليل المذكور.

مثال

التشفيررسالة نصية قصيرة أصلية: RSA.
يقوم المستلم بتعيين التشفير بالخصائص ن = pq = 527، أين ص = 17, ف = 31و φ (ن) = (р –1) (ف - 1) = 480. كمفتاح عام هيتم اختيار رقم يمثل جريمة مشتركة معه φ (ن), ه = 7. لهذا الرقم ، باستخدام خوارزمية إقليدس الموسعة ، تم العثور على الأعداد الصحيحة شو الخامس، إرضاء العلاقة ه ∙ ش + φ (ن) ∙ ت = 1:

480=7∙68+4,
7=4∙1+3,
4=3∙1+1,
1=4–3∙1=4–(7–4∙1)∙1=4∙2–7∙1=(480–7∙68)∙2–7∙1=480∙2–7∙137,
الخامس = 2 ، ش = –137.

بقدر ما –137≡343 (طراز 480)، ومن بعد د = 343.

فحص: 7 ∙ 343 = 2401≡1 (طراز 480).

يتم تقديم رسالة نصية كسلسلة من الأرقام الواردة في الفاصل الزمني . لهذه الرسالة ص, سو أمشفرة كأرقام ثنائية 5 بت. يتم استخدام الأرقام التسلسلية لهذه الأحرف في الأبجدية الإنجليزية في التمثيل الثنائي:

ص = 18 10 = (10010) 2, S = 19 10 = (10011) 2,
أ = 1 10 = (00001) 2.

ثم RSA = (100101001100001) 2. يعطي تقسيم النص إلى كتل محدودة الطول تمثيلاً لكتلتين: RSA = (100101001) ، (100001) = (M 1 = 297 ، M 2 = 33).

كتل مشفرة بالتسلسل من النص المصدر م 1 \ u003d 297, م 2 \ u003d 33:
y 1 \ u003d E k (M 1) \ u003d M 1 e ≡297 7 (mod527) \ u003d 474.

استخدمنا هنا:

297 7 = ((297 2) 3) 297 درجة (طراز 527) = (200 3 (نموذجي 527) 297) (نموذج 527) = 474,
y 2 \ u003d E k (M 2) \ u003d M 2 e ≡33 7 (mod527) \ u003d 407.

يتم الحصول على النص المشفر ، مثل النص الأصلي ، في شكل كتلتين: ص 1 = 474; ص 2 = 407.

فك التشفيريبدو أنه سلسلة من الإجراءات د ك (ص ط) = (ص ط) د = (ص ط) 343 (عصري 527), أنا = 1،2.

حسابات الأُس دمن الأنسب تنفيذ ، تمثيل الأس بشكل مبدئي كمجموع قوى رقم 2 ، يسمى: 343=256+64+16+4+2+1 .

باستخدام هذا التمثيل الأس د = 343، نحن نحصل:

474 2 ≡174 (طراز 527) ،
474 4 ≡237 (طراز 527) ،
474 8 ≡307 (mod527) ،
474 16 ≡443 (طراز 527) ،
474 32 ≡205 (طراز 527) ،
474 64 392 (طراز 527) ،
474128-307 (mod527) ،
474256 ≡443 (طراز 527) ،
وأخيرا 474343 (طراز 527) = (443 ∙ 392 ∙ 443 ∙ 237 ∙ 174 474) (طراز 527) = 297.

يتم حساب القيمة بالمثل 407343 (طراز 527) = 33.

يوفر التبديل إلى التمثيل الحرفي للرسالة التي تم فك تشفيرها: RSA.

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

هجوم على تشفير RSA

لنأخذ مثالاً على هجوم على تشفير RSA. دعنا نستخدم بيانات المثال الوارد في الصفحات 313-315 في الكتاب المدرسي "أساسيات التشفير" بواسطة A.P. ألفيروف ، أ. زوبوف ، أ. كوزمين ، أ.ف. Cheremushkin ، موسكو. "Helios ARV" ، 2001.

يظهر فشل (عدم مقبولية) معلمات النظام المحددة في هذا المثال بسهولة من خلال الحسابات التي تنفذ هجوم القراءة بدون مفتاح للنص المصدر. جوهر مثل هذا الهجوم على النحو التالي. يتم إعطاء المفتاح العام لتشفير RSA ( ه = 7, ن = 527) والنص المشفر. في المثال ، يتم تمثيل النص المشفر بكتلتين
ص \ u003d (ص 1 \ u003d 474 ، ص 2 \ u003d 407).

يتم مهاجمة كل كتلة مشفرة بشكل فردي ، نهاجم أولاً ص 1 = 474، بعد فك تشفيرها ، نهاجم كتلة أخرى ص 2 = 407.

ثم يتم تشكيلها عن طريق التشفير المتكرر مع حفظ نتائج خطوتين متتاليتين من خوارزمية الهجوم واستخدام المفتاح العام سلسلة من القيم العددية أنا, ص 1 = صالنص المشفر المتاح.

في خوارزمية هجوم النص المشفر ، يتم تحديد رقم الخطوة التالية ي، لأي منهم y i e j (mod n) = (y i e j – 1 (mod n)) e (mod n) = y i, أنا> 1. من العلاقة الأخيرة نرى ذلك عند الارتقاء إلى قوة هالقيم (y i e j – 1 (mod n))اتضح shifortext الأولي ص أنا = ص 1.

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

هجوم على الكتلة الأولى ص 1 = 474نص مشفر.
الخطوة 1:نبسب 474 7 (mod527) = 382;
الخطوة 2:& nbsp 382 7 (mod527) = 423;
الخطوه 3:& nbsp 423 7 (mod527) = 297;
الخطوة 4: & nbsp تقوم هذه الخطوة بتشفير نص المصدر الذي تم العثور عليه بالفعل ، ولكن يجب تنفيذه لأن المهاجم لا يعرف نص المصدر. علامة اكتمال الهجوم هي مصادفة القيمة الأولية للنص المشفر ( 474 ) ونتيجة الخطوة الرابعة من التشفير. هذا هو بالضبط نوع المصادفة التي تحدث.

297 7 (طراز 527) = 474تلقي كتلة النص المشفر الأولي (الأولى). اكتمل الهجوم على الكتلة الأولى بنجاح ص 1 = 474. النتيجة السابقة للخطوة 3 هي نص عادي م 1 \ u003d 297.

ن = 527 ص = 297مودولو ن = 527. إنه مكتوب على هذا النحو ص أنا \ u003d ص 1 \ u003d 297. نحن نشكل مخلفات القوة
(((297 7 (mod527)) 7 (mod527)) 7 (mod527)) 7 = 297.

هجوم على الكتلة الثانية ص 2 = 407نص مشفر.
الخطوة 1:نبسب 407 7 (mod527) = 16;
الخطوة 2:& nbsp 16 7 (mod527) = 101;
الخطوه 3:& nbsp 101 7 (mod527) = 33;
الخطوة 4:نبسب 33 7 (mod527) = 407.

مرة أخرى ، في الخطوة الثالثة ، يتم الحصول على كتلة النص المصدر ( م 2 \ u003d 33) ، لكن المهاجم لا يعرف ذلك ، ويقوم بالخطوة التالية (الخطوة الرابعة) ، والنتيجة هي ( 407 ) يطابق النص المشفر الأولي ص 2 = 407.

أساسا في حلقة البقايا modulo ن = 527نفذت دورة معالجة قصيرة للخصم ص = 33مودولو ن = 527. إنه مكتوب على هذا النحو ص أنا \ u003d ص 2 \ u003d 33.
نحن نشكل مخلفات القوة ((33 7 (mod527)) 7 (mod527)) 7 (mod527) = 33.

نتيجة الهجوم (النص الأصلي م 1 \ u003d 297, م 2 \ u003d 33) من خلال التشفير الثلاثي للنص المشفر المحدد. من الصعب تخيل نجاح أكبر للنص المشفر المهاجم.

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

لا شيء من البريد المعطى قادر على تشفير النصوص العادية الممثلة بالأرقام
187 , 341 , 154 و 373 .

مثال (عدم القدرة على تشفير قيم بعض النصوص المصدر)

دع النصوص المصدر يتم تمثيلها بأربع كتل ص = (ص 1 = 154 ، ص 2 = 187 ، ص 3 = 341 ، ص 4 = 373). عارض هيمكن أن يكون المفتاح العام للتشفير أي رقم أولي نسبيًا باستخدام وظيفة أويلر φ (ن) = φ (527) = 480. ومع ذلك ، بالنسبة للحالة قيد النظر ، المفتاح العمومي هيمكن تعيينها بشكل تعسفي. في الواقع ، دعنا ه = 2 ، 4 ، 7 ، 9 ، 17 ، 111ومن بعد:

154 2 (طراز 527) = 1;
154 4 (طراز 527) = 1;
154 7 (طراز 527) = 154;
154 9 (طراز 527) = 154;
154 17 (طراز 527) = 154;
154111 (طراز 527) = 154;
187 2 (طراز 527) = 187;
187 4 (طراز 527) = 187;
187 7 (طراز 527) = 187;
187 9 (طراز 527) = 187;
187 17 (طراز 527) = 187;
187111 (طراز 527) = 187;
341 2 (طراز 527) = 341;
341 4 (طراز 527) = 1;
341 7 (طراز 527) = 341;
341 9 (طراز 527) = 341;
341 17 (طراز 527) = 341;
341111 (طراز 527) = 341;
373 2 (طراز 527) = 1;
373 4 (طراز 527) = 373;
373 7 (طراز 527) = 373;
373 9 (طراز 527) = 373;
373 17 (طراز 527) = 373;
111 373 (طراز 527) = 373.

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