تعليقات

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


قدم عالم الرياضيات الألماني سي. ف. غاوس مفهوم التطابق في الفصل الأول من عمله "Disquitiones Arithmeticae" ، الذي نُشر عام 1801. هذا المفهوم أساسي في ترميز وفك تشفير المفاتيح في نظام RSA. تم تطوير نظام تشفير المفتاح العمومي ، المسمى RSA ، بواسطة العلماء R. Rivest و A. Shamir و L. Adleman.

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

(1) عدد كبير Nوهو نتاج رقمين متميزين ص و فأي N = ص۰ف.

(2) عدد صحيح و، والمعروفة باسم مفتاح الترميز ، الذي يفي الخصائص التالية:

القاسم المشترك الأقصى (MDC) بين و والمنتج (ص - 1)۰(ف -1) هي 1 ، و MDC

في ما بين و و N هو أيضا 1.

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

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

و۰D ≡ 1 (وزارة الدفاع (ص -1)۰(ف - 1)).

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

في العمود السابق قمنا بتشفير الرسالة المفتاح العام باستخدام نظام RSA مع

N = 2.537 = 43•59, ص = 43, ف = 59 ومع مفتاح التشفير و = 13.

أولاً ، لاحظنا ذلك N = 2.537 يحتوي على 4 أرقام ولذا فإننا نقسم النص إلى أزواج من الحروف: PU BL IC KE Y وأكمل المجموعة الأخيرة بالحرف C: PU BL IC KE YC.

باستخدام جدول التحويل الذي يربط الأرقام الطبيعية بأحرف الأبجدية ، فإن كتل الرسالة المحولة هي: 1520 0111 0802 1004 2402. بهذه الطريقة ، سيتلقى المتلقي الرسالة المشفرة: 0095 1648 1410 1299 0811.

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

هل هناك طريقة لتحديد Dإذا و, ص و ف معروفة. ومع ذلك ، إذا ص و ف غير معروفين ، D لا يمكن تحديده. يكمن أمان نظام تشفير RSA في هذه الحقيقة.

إذا ص و ف كبيرة للغاية على سبيل المثال أكبر من 10200ثم حدد هذه الأرقام الأولية في وقت معقول ، وهو ما يعادل العوملة N = ص۰ف,قد يكون أكبر من قدرة أجهزة الكمبيوتر العملاقة الأسرع.

هدفنا هو تحديد Dمثل هذا و۰D ≡ 1 (وزارة الدفاع (ص - 1)۰(ف - 1)) ، وبعبارة أخرى D هو معكوس و وحدة (ص - 1)۰(ف - 1).

تتكون الطريقة من استخدام خوارزمية Euclid المطبقة على المفتاح و الترميز والعدد (ص - 1)۰(ف - 1). كما و و (ص - 1)۰(ف - 1) تكون أولية لبعضها البعض ، MDC بينهم 1. أولاً ، نمر بجميع خطوات خوارزمية Euclid لتحديد MDC التي في هذه الحالة هي 1.

بواسطة الخوارزمية الإقليدية علينا أن

(ص - 1)۰(ف - 1) = ف1۰و+ ص2, 0 ≤ ص2< و.

كيف نعرف أن MDC ((ص - 1)۰(ف - 1), و) = 1 ، نواصل تطبيق الخوارزمية الإقليدية حتى نحصل على بقية القسمة تساوي 1. لذلك ، فإننا نقوم بتقسيم و بواسطة ص2 وهكذا حتى نحصل على بقية 1:

و = ف2۰ ص2 + ص3, 0 ≤ ص3< ص2

ص2 = ف3۰ ص3+ ص4,0 ≤ ص4< ص3

صن-4 = فن 3۰ صن 3 + صن 2,0 ≤ صن 2 < صن 3

صن 3 = فن 2۰ صن 2 + صن 1,0 ≤ صن 1 < صن 2

صن 2 = فن 1۰ صن 1 + 1,0 ≤ 1< صن 1.

الآن باستخدام خوارزمية إقليديا في الاتجاه المعاكس يمكننا حساب D مثل هذا

و۰D ≡ 1 (وزارة الدفاع (ص -1)۰(ف - 1)).

لذلك، D هذا هو مفتاح فك التشفير.

لاحظ أن:

<>

1 = صن 2 - فن 1۰<>

ص<>

ن 1<>

(1)

<>

ص<>

ن 1<>

= صن 3 - فن 2۰<>

ص<>

ن 2<>

(2)

<>

ص<>

ن 2 <>

= صن-4 - فن 3۰<>

ص<>

ن 3<>

(3)

ص4 = ص2-ف3۰ ص3 (ن - 3)

ص3= و - ف2۰ ص2, (ن - 2)

ص2 = (ص - 1)۰(ف - 1) - ف1و (ن - 1)

تجاوز قيمة صن 1 من (2) إلى (1) نحصل عليه

1 = (1 + فن 1۰فن 2صن 2 - فن 1۰صن 3

والاستعاضة في هذا المساواة قيمة صن 2 من (3) نحصل عليه

صن = - (فن 3 + فن 1۰فن 2۰فن 3 + فن 1صن 3 + (1 + فن 1۰فن 2صن-4.

لذلك نحن نمضي على التوالي حتى نحصل على العدد الصحيح في النهاية D مثل هذا

و۰D ≡ 1 (وزارة الدفاع (ص -1)۰(ف - 1)).

في مثالنا لدينا:

N = 2.537 = 43۰59, ص = 43, ف = 59 و (ص - 1)۰(ف - 1) = 42۰58 = 2،436 و و = 13.

استخدام خوارزمية Euclid لتحديد MDC بين (ص - 1)۰(ف - 1) = 2،436 و و = 13 حصلنا على:

2.436 = 187۰13 + 5, 13 = 2۰5 + 3, 5 = 1۰3 + 2, 3 = 1۰2 + 1.

الآن ، باستخدام خوارزمية Euclid في الاتجاه المعاكس ، نحصل على:

1 = 3 - 1۰2, 2 = 5 - 1۰3, 3 = 13 - 2۰5, 5 = 2436 - 187۰13

لذلك ، استبدال كما هو موضح أعلاه ، لدينا:

1 = 3 - 1۰2 = 3 - 1۰( 5 - 1۰3) = 3 - 1۰5 + 1۰3 = - 5 + 2۰3;

1 = - 5 + 2۰3 = - 5 + 2۰( 13 - 2۰5) = - 5 + 2۰13 - 4۰5 = 2۰13 - 5۰5;

1 = 2۰13 - 5۰5 = 2۰13 - 5۰( 2.436 - 187۰13) = 2۰13 - 5۰2.436 + 935.۰13 =

= 937۰13 - 5۰2.436.

وبالتالي ، نحصل على 1 = 937۰13 - 5۰2.436 والذي يعني 937۰13 = 5۰2.436 +1.

لذلك ، 13۰937 ≡ 1 (mod 2.436) ، أي و37937 ≡ 1 (mod (ص -1)۰(ف - 1)).

نستنتج ذلك D = 937.

في العمود التالي سوف نقوم بفك تشفير الرسالة.

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

<


فيديو: قنبلة الرياضيات وتجربة كازيمير - رواد العلم (ديسمبر 2021).