بالتفصيل

فرضية ريمان والإنترنت II


في عام 1977 ، اقترح العلماء R. Rivest و A. Shamir و L. Adleman نظام تشفير مفتاح عمومي يسمى RSA. يستخدم هذا النظام بعض الأفكار الأولية من نظرية الأعداد.

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

قدم غاوس مفهوم التطابق في الفصل الأول من عمله "Disquitiones Arithmeticae" الذي نشر في عام 1801. قدم غاوس ، بالتزامن مع مفهوم التطابق ، تدوين "،" ، مما جعل المفهوم تقنية قوية في نظرية الجبر والنظرية. دعنا نذهب إلى التعاريف.

ونحن نعتبر اثنين من الأعداد الصحيحة ال, ب و ن عدد صحيح إيجابي. إذا ن منقسم ال - ب، ثم نقول ذلك ال غير متطابق مع ب مودولو ن، وكتبنا الب (وزارة الدفاع ن).

على سبيل المثال:

37 ≡ 2 (mod 5) ، لأن 5 يقسم 37 - 2 = 35 ،

27 ≡ 3 (mod 4) ، لأن 4 يقسم 27 - 3 = 24 ،

7 ≡ 7 (mod 4) ، لذلك 4 قسمة 7 - 7 = 0.

لذلك، الب (وزارة الدفاع ن) يعني ذلك ن منقسم ال - ب. لذلك هناك عدد صحيح ك مثل هذا ال - ب = KN من خلال تعريف القسمة. على سبيل المثال ، 37 ≡ 2 (وزارة الدفاع 5) يعني أن هناك ك (= 7) بحيث 37 - 2 = 35 = 7 • 5.

بالنظر إلى الأعداد الصحيحة ال و ن، نعلم من قسم الخوارزمية أن هناك أعداد صحيحة ف و ص على التوالي ، حاصل الباقي ، بحيث: ال = QN + صحيث 0 ≤ ص < ن. الشعار، ال - ص = QNأي ن منقسم ال - ص. لذلك ، من خلال تعريف التطابق الص (وزارة الدفاع ن).

الباقي ص يمكن أن نفترض أي قيمة بين 0 و ن - 1. وبالتالي ، فإننا نستنتج أن كل عدد صحيح ال هو وحدة متطابقة ن لواحدة من القيم بين 0 ، 1 ، 2 ، ... ، ن - 1. المجموعة {0 ، 1 ، 2 ، ... ، ن - 1} من الأعداد الصحيحة م التي هي بقايا الانقسامات وحدة ن، ويسمى وحدة فئة النفايات ن. إذا كنا إصلاح ن = 7 ، وبالتالي فإن فئة الوحدة 7 تحتوي على 7 عناصر بالضبط ، وهي: 0 ، 1 ، 2 ، ... ، 6. لذلك ، أيا كان عدد صحيح ، فإنه يتوافق مع عنصر واحد من وحدة 7 الفئة.

على سبيل المثال ، يتم تمثيل 20 في 6 في فئة بقايا وزارة الدفاع 7 ، منذ 20 ≡ 6 (mod 7).

فكرة التطابق موجودة في حياتنا اليومية إذا كنا نعتقد أن الساعات تحدد وحدة الساعات 12 ، يتم قياس أيام الأسبوع في الوحدة النمطية 4 ، وتتبع أشهر السنة نمط الوحدة 12. نظرًا للعديد من الخصائص المتشابهة بين التطابقات والمساواة ، اختار غاوس رمز "≡" للإشارة المطابقة.

لاحظ ذلك الال (وزارة الدفاع ن) وإذا الب (وزارة الدفاع ن) ثم بال(وزارة الدفاع ن). عمليات الضرب والضرب تتصرف على النحو التالي.

إذا الب (وزارة الدفاع ن) و جد (وزارة الدفاع ن) ثم:

ال + ج ب + د (وزارة الدفاع ن),

ال ج ب د (وزارة الدفاع ن),

الصبص (وزارة الدفاع ن).

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

لتحديد بقية تقسيم ال بواسطة ن يكفي للعثور على عدد صحيح ص مثل هذا الص (وزارة الدفاع ن) حيث 0 ص < ن. على سبيل المثال ، لتحديد بقية تقسيم 310 قبل 13 قدمنا ​​310 ثم قسّمه على 13 ، وهذا ليس بالأمر السهل. ومع ذلك ، فإن مفهوم التطابق يسهل إلى حد كبير هذا الإجراء. أولاً نلاحظ أن:

33 ≡ 1 (13 وزارة الدفاع) ، وهذا سهل!

الآن عن طريق رفع كل شيء إلى المكعب ، نحصل عليه

(33)3 ≡ (1)3 وزارة الدفاع 13 أي 39 ≡ 1 (13 وزارة الدفاع).

إذا ضاعفنا طرفي التطابق بمقدار 3 ، فعندئذ نحصل على 310 ≡ 3 (13 وزارة الدفاع).

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

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

لتشفير نص وفقًا لنظام RSA ، تحتاج إلى:

(1) عدد كبير Nوهو نتاج اثنين من أبناء عمومة متميزة ص و فأي N = ع • ف.

(2) عدد صحيح و، والمعروفة باسم مفتاح الترميز ، والذي يفي بالخصائص التالية: القاسم المشترك الأكبر (MDC) بين و والمنتج (ص - 1) (ف - 1) هي 1 ، و MDC بينهما و و N هو أيضا 1.

لفك تشفير نص ، وفقًا لنظام RSA ، تحتاج إلى:

(3) عدد صحيح D، والمعروفة باسم مفتاح فك التشفير ، والتي تلبي الشرط:

هاء • د ≡ 1 (وزارة الدفاع (ص -1) (ف -1)).

لاحظنا أن العلاقة بين و و D متماثل ، وهذا هو ، إذا D هو مفتاح فك التشفير ل وثم و هو مفتاح فك التشفير ل D.

دعونا ترميز الرسالة المفتاح العام باستخدام نظام RSA مع N = 2537 ومفتاح التشفير و = 13. أولاً ، نلاحظ ذلك N = 43.59 حيث 43 و 59 أعداد أولية.

وبالتالي ، MDC (13 ، (43 - 1) • (59 - 1)) = MDC (13 ، 42 • 58) = 1 ، لأن العدد الصحيح 13 لا يقسم 42 ولا 58 ؛ MDC (13 ، 2537) = 1 ، لأن 13 و 43 و 59 (2537 = 43 • 59) هي أعداد أولية. الآن نقوم بتحويل النص باستخدام جدول مطابقة رقم الحرف:

A = 00 ، B = 01 ، C = 02 ، D = 03 ، ... ، X = 23 ، Y = 24 ، Z = 25.

كما N = 2537 يحتوي على 4 أرقام ، نلف النص في أزواج من الحروف:

PU BL IC KE Y

وأكمل الكتلة الأخيرة بالحرف C الحصول على

<>

PU BL IC KE YC<>

.

باستخدام جدول التحويل أعلاه ، فإن كتل الرسائل المحولة 5 هي:

1520 0111 0802 1004 2402.

سوف نسمي B الكتلة المكونة من أربعة أرقام. والخطوة التالية هي حساب قيمة كل من الكتل الأربعة المكونة من أرقام التي تم رفعها إلى الأس 13 (mod 3127) ، أي في حالة إعطاء كتلة B ، نريد تحديد C بحيث C = P13 (وزارة الدفاع 2537).

على سبيل المثال ، عندما نرمز للكتلة الأولى ، يتعين علينا حل C ≡ 152013 ص (وزارة الدفاع 2537). ثم نمضي على النحو التالي:

<>

15202 = 2310400 = 910 • 2537 + 1730 ≡ 1730 (mod 2537) ؛

<>

15204 = 17302 = 2،992،900 = 1179 • 2537 + 1777 ≡ 1777 (mod 2537) ؛

<>

15208 = 17772 = 3،157،729 = 1244 • 2537 + 1701 ≡ 1701 (mod 2537) ؛

<>

152012 = 15208.• 15204 = 1701 • 1777 = 3.022.677 = 1191 • 2537 + 1110 =

<>

= 1110 (mod 2537) ؛

152013 = 152012 • 1520 = 1110 • 1520 = 1،687.200 = 665 • 2537 + 95 = 95 (mod 2537).

وبالتالي ، فإن ترميز 1520 هو 0095.

يتم تشفير كتل الرسائل الأخرى بنفس الطريقة ، أي أن كل كتلة تتكون من أربعة أرقام ترتفع إلى القدرة 13 (mod 2537). لذلك ، سيتلقى المتلقي الرسالة المشفرة:

0095 1648 1410 1299 0811.

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

العودة إلى الأعمدة

<


فيديو: حل حدسية ريمان (شهر اكتوبر 2021).