فك تشفير رسا

Question

كيف يمكننا فك تشفير رسالة رسا إذا كان لدينا فقط المفتاح العمومي?

على سبيل المثال, الرسالة:21556870,12228498 المفتاح العام: (e = 15852553, n = 44331583)

أعلم أن هذه الصيغ موجودة:

gcd(e, φ(n)) = 1
ed mod φ(n) = 1

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

Answer 1

"كيف يمكننا فك تشفير رسالة رسا إذا كان لدينا فقط المفتاح العمومي?"

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

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

حاول بجدية أكبر قبل النظر إلى الإجابة أدناه.

---

المفتاح العام: (e = 15852553, n = 44331583)

دعونا عامل n.هنا هو برنامج بيثون بسيط.

def factor(n):
    for i in range(2, n-1):
        if n % i == 0:
            print(str(n) + " = " + str(i) + " * " + str(n // i))
            break

تشغيل factor(44331583), ، نحصل على ذلك 44331583 = 5003 * 8861.

لذا φ(n) = (5003 - 1) * (8861 - 1) = 44317720

---

أوجد معكوس e مودولو φ(n).هنا هو برنامج بيثون بسيط.

def inverse(e, phi):
    """ display the inverse of e modulo phi """

    for i in range(1, phi):
        if i * e % phi == 1:
            print(str(e) + " * " + str(i) + " = 1 (mod " + str(phi) + ")")
            break

تشغيل inverse(15852553, 44317720), ، نحصل على ذلك 15852553 * 1951097 = 1 (mod 44317720).وهذا هو ، معكوس e مودولو φ(n) هو d=1951097.

لذا ، فإن المفتاح الخاص المقابل هو (d = 1951097, n = 44331583).

---

حساب m**d (mod n) لفك تشفير رسالة رسا (ويعرف أيضا باسم.النص المشفر) m.ها هي دالة الأس المعيارية الشائعة.

def modulo_pow(base, exponent, modulus):
    """ display the result of base ** exponent % modulus """

    exp = exponent
    result = 1
    b = base % modulus

    while exp > 0:
        if exp % 2 == 1:
            result = (result * b) % modulus
        exp = exp >> 1
        b = (b * b) % modulus

    print(str(base) + " ** " + str(exponent)
          + " = " + str(result) + " (mod " + str(modulus) + ")")

تشغيل modulo_pow(21556870, 1951097, 44331583) و modulo_pow(71, 15852553, 44331583), ، حصلنا ، على التوالي,

21556870 ** 1951097 = 71 (mod 44331583)
12228498 ** 1951097 = 111 (mod 44331583)

وبالتالي ، فإن الرسالة التي تم فك تشفيرها هي 71,111.يمكنك أن تجد ما يعنيه?

Answer 2

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