تكسير مفاتيح RSA قصيرة

Question

بالنظر إلى مفاتيح RSA التالية ، كيف يمكن للمرء أن يحدد قيم قيم ص و س نكون؟

Public Key: (10142789312725007, 5)
Private Key: (10142789312725007, 8114231289041741)

Answer 1

أعطاك معلمك:

المفتاح العام: (10142789312725007 ، 5)

وهو ما يعني

n = 10142789312725007
e = 5 

أين ن هو المعامل و ه هو الأسس العام.

بالإضافة إلى ذلك ، تعطيك

المفتاح الخاص: (10142789312725007 ، 8114231289041741)

وهذا يعني أن

 d = 8114231289041741

أين د هو الأسس فك التشفير الذي يجب أن يظل سرا.

يمكنك "كسر" RSA من خلال معرفة كيفية عوامل "N" في "P" و "Q" العوامل الأولية:

n = p * q

من المحتمل أن تكون أسهل طريقة هي التحقق من جميع الأرقام الفردية التي تبدأ أسفل الجذر التربيعي لـ N:

Floor[Sqrt[10142789312725007]] = 100711415

ستحصل على العامل الأول في 4 محاولات:

10142789312725007 mod 100711415 = 100711367
10142789312725007 mod 100711413 = 100711373
10142789312725007 mod 100711411 = 100711387
10142789312725007 mod 100711409 = 0 <-- Winner since it evenly divides n

اذا لدينا

 p = 100711409

حاليا،

 q = n / p 
   = 10142789312725007 / 100711409
   = 100711423

لماذا هذا مهم؟ انه بسبب د هو رقم خاص مثل

d = e^-1 mod phi(n)
  = e^-1 mod (p-1)*(q-1)

يمكننا التحقق من هذا

d * e = 40571156445208705 = 1 mod 10142789111302176

هذا مهم لأنه إذا كان لديك رسالة نصية عادي م ثم النص المشفر

c = m^e mod n

وأنت فك تشفيرها

m = c^d = (m^e)^d = (m^(e*d)) = (m^(e*e^-1)) = m^1 (mod n)

على سبيل المثال ، يمكنني "تشفير" الرسالة 123456789 باستخدام مفتاح المعلم العام الخاص بك:

m = 123456789

هذا سوف يعطيني النص المشفر التالي:

c = m^e mod n 
  = 123456789^5 mod 10142789312725007
  = 7487844069764171

(لاحظ أن "E" يجب أن تكون أكبر بكثير في الممارسة لأنه بالنسبة للقيم الصغيرة من "M" ، فأنت لا تتجاوز حتى n)

على أي حال ، لدينا الآن "C" ويمكننا عكسها بـ "D"

m = c^d mod n
  = 7487844069764171^8114231289041741 mod 10142789312725007
  = 123456789

من الواضح أنه لا يمكنك حساب "7487844069764171^8114231289041741" مباشرة لأنه يحتوي على 128،808،202،574،088،302 رقمًا ، لذلك يجب عليك استخدام الأسعار المعيارية حيلة.

في العالم الحقيقي"، ن من الواضح أنه أكبر بكثير. إذا كنت ترغب في رؤية مثال حقيقي على كيفية استخدام HTTPS RSA تحت الأغطية باستخدام 617 رقمًا ن و ه من 65537 ، انظر منشور مدونتي "أول ميلي ثانية من اتصال HTTPS."

Answer 2

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

sqrt(10142789312725007) = 100711415.9999997567

أول برايم أدناه هو 100711409 ، فقط 6 أسفل SQRT (N).

10142789312725007 / 100711409 = 100711423 

لذلك هاتان عاملان لـ N. جعل أستاذك سهلاً للغاية - الحيلة هي إدراك أنه لا أحد يختار أ صغير P أو Q ، لذا فإن بدء الشيك الخاص بك من الأسفل (كما في البرنامج النصي Python الذي نشره شخص ما) هو فكرة سيئة. إذا كانت عملية باليد ، يجب أن تقع P و Q الكبيرة بالقرب من SQRT (N).

Answer 3

هناك العديد من الخوارزميات السريعة لحل مشكلة العوملة n معطى n, e, ، و d. يمكنك العثور على وصف جيد لواحد من هذه الخوارزمية في كتيب التشفير المطبق ، الفصل 8, ، القسم 8.2.2. يمكنك العثور على هذه الفصول عبر الإنترنت للتنزيل المجاني هنا. الخوارزمية هي في الأساس تفصيل دقيق ل إجابة Henno Brandsma لهذا السؤال بالذات.

تحديث 25 سبتمبر 2019:

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

يلاحظ ذلك عادة e صغير. في الواقع e هو دائما 65537. في حالة ذلك e هل يمكنك تطوير معادلة تربيعية في البرايم غير المعروف p وبالتالي حلها بسهولة باستخدام EG الصيغة التربيعية. للمضي قدما ، دعنا نضبط x = p وحل ل x, ، فقط للتمسك بالاتفاقية. نحن نعلم ذلك ed = 1 mod phi(n), ، أو مكافئed - 1 = k * (p-1)*(q-1). الآن الإعداد x=p, ، وبالتالي n/x=q, ، مضاعفة كلا الجانبين x وإعادة ترتيب المصطلحات لدينا
k*x² + (d*e - k*n - k - 1)*x + k*n = 0.
الآن لدينا معادلة فأس النموذج² + bx + c = 0 ويمكننا حلها لـ x باستخدام الصيغة التربيعية. حتى نتمكن من تجربة قيم k في نطاق صغير حوله e ويجب أن يكون هناك حل صحيح واحد فقط للتربيعة ، وهو حل K الصحيح.

ملحوظات:

1. يجب أن يكون كل شيء عددًا صحيحًا ، وبالتالي يجب أن يكون التمييز مربعًا مثاليًا أو يمكننا تجاهل K وتجربته التالية. أيضا ، يجب أن يكون البسط قابل للقسمة 2*k.
2. في بعض الأحيان يتم استخدام وظيفة Carmichael Lambda بدلاً من وظيفة Euler PHI. هذا يعقد الأمور قليلاً لأنه يجب علينا الآن تخمين أيضًا g = gcd(p-1, q-1). g حتى دائمًا ، غالبًا ما يكون 2 ، وهو دائمًا ما يكون مضاعفًا صغيرًا من 2.

تحديث 26 سبتمبر 2019:

العثور على k في الواقع سهل جدا عندما e صغير. عن طريق أخذ المعادلةed - 1 = k * (p-1)*(q-1) وتقسيم كلا الجانبين n من السهل إلى حد ما رؤية ذلك floor((ed-1)/n) + 1 == k. الآن باستخدام المعادلات 31 و 32 من MJ Wiener's "تحليل Cryptanalysis of RSA Secret Secrets" يمكن للمرء أن يتعافى مباشرة p و q.

Answer 4

ولفرام ألفا يخبرني أن العوامل هي 100711409 و 100711423

لقد كتبت للتو سيناريو بيثون ساذج ليحققه. كما أشار Amdfan ، فإن البدء من الأعلى هو نهج أفضل:

p = 10142789312725007
for i in xrange(int(p**0.5+2), 3, -2):
    if p%i == 0:
        print i
        print p/i
        break

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

Answer 5

يخبرك تعريف RSA أن المعامل n = pq. أنت تعرف n لذلك تحتاج فقط إلى العثور على رقمين p و q هذا يتضاعف لإنتاج n. هل تعلم أن p و q هي Prime ، لذلك هذه هي مشكلة العوامل الأولية.

يمكنك حل هذا بالقوة الغاشمة لأعداد صغيرة نسبيًا ، لكن الأمن العام لـ RSA يعتمد على حقيقة أن هذه المشكلة قابلة للشفاء بشكل عام.

Answer 6

فيما يلي تطبيق Java لطريقة العوملة السريعة من كتيب التشفير التطبيقي الفصل 8 القسم 8.2.2 (بفضل Gregs للعثور عليه):

/**
 * Computes the factors of n given d and e.
 * Given are the public RSA key (n,d)
 * and the corresponding private RSA key (n,e).
 */
public class ComputeRsaFactors
{
    /**
     * Executes the program.
     *
     * @param args  The command line arguments.
     */
    public static void main(String[] args)
    {
        final BigInteger n = BigInteger.valueOf(10142789312725007L);
        final BigInteger d = BigInteger.valueOf(5);
        final BigInteger e = BigInteger.valueOf(8114231289041741L);

        final long t0 = System.currentTimeMillis();

        final BigInteger kTheta = d.multiply(e).subtract(BigInteger.ONE);
        final int exponentOfTwo = kTheta.getLowestSetBit();

        final Random random = new Random();
        BigInteger factor = BigInteger.ONE;
        do
        {
            final BigInteger a = nextA(n, random);

            for (int i = 1; i <= exponentOfTwo; i++)
            {
                final BigInteger exponent = kTheta.shiftRight(i);
                final BigInteger power = a.modPow(exponent, n);

                final BigInteger gcd = n.gcd(power.subtract(BigInteger.ONE));
                if (!factor.equals(BigInteger.ONE))
                {
                    break;
                }
            }
        }
        while (factor.equals(BigInteger.ONE));

        final long t1 = System.currentTimeMillis();

        System.out.printf("%s %s (%dms)\n", factor, n.divide(factor), t1 - t0);
    }


    private static BigInteger nextA(final BigInteger n, final Random random)
    {
        BigInteger r;
        do
        {
            r = new BigInteger(n.bitLength(), random);
        }
        while (r.signum() == 0 || r.compareTo(n) >= 0);
        return r;
    }
}

الناتج النموذجي هو

100711423 100711409 (3ms)

Answer 7

يمكن أن تأتي هاتان الورقتان مفيدة

• Andrej Dujella - متغير من هجوم Wiener على RSA
• Andrej Dujella - الكسور المستمرة و RSA مع أسس سري صغير

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

Answer 8

الخوارزمية للقيام بذلك هي (وهذا سيعمل من أجل أي مثال ، ليس فقط هذا صغير يمكن أخذها في الاعتبار بسهولة من قبل أي جهاز كمبيوتر):

ed - 1 هو مضاعف من phi(n) = (p-1)(q-1), ، وكذلك على الأقل مضاعف 4.
ed - 1 يمكن حسابها على أنها 40571156445208704 التي تساوي 2^7 * 316962159728193، ونحن ندعو s=7 و t = 316962159728193. (بشكل عام: أي رقم زوجي هو قوة 2 أضعاف رقم فردي). اختر الآن في [2,n-1) عشوائيا ، وحساب (بواسطة Modulo المتتالية n) الترتيبa^t (mod n), a^(2t) (mod n), a^(4t) (mod n).. حتى على الأكثر a^((2^7)*t) (mod n), ، حيث يضمن آخرها أن يكون 1 ، عن طريق بناء e و d.

نبحث الآن عن الأول 1 في هذا التسلسل. واحد قبل أن يكون إما +1 أو -1(جذر تافهة من 1 ، mod n) ونحن نعيد مع أرقام مختلفة أو بعض x الذي لا يساوي +1 أو -1 mod n. في الحالة الأخيرة gcd(x-1, n) هو مقسوم غير تافهة n, ، وهكذا p أو q, ، وقد انتهينا. يمكن للمرء أن يوضح أن عشوائيًا أ سوف يعمل مع احتمال حوالي 0.5 ، لذلك نحن بحاجة إلى بضع محاولات ، ولكن ليس الكثير بشكل عام.

Answer 9

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

Answer 10

آسف على مستحضر الأرواح ، لكن صديقًا سألني عن هذا ، وبعد أن أشير إليه هنا ، أدركت أنني لم يعجبني حقًا أي من الإجابات. بعد عودة المعامل والحصول على الأعداد الأولية (P و Q) ، تحتاج إلى العثور على TOTIENT ، وهو (p-1)*(q-1).

الآن ، للعثور على الأسس الخاص ، تجد عكس الأسس العام Mod the Totient.

public_exponent * private_exponent = 1 mod totient

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

لقد كتبت بعض الكود:

// tinyrsa.c
//
// apt-get install libgmp-dev
// yum install gmp-devel
//
// gcc tinyrsa.c -o tinyrsa -lm -lgmp

#include<stdio.h>
#include<gmp.h>

int main()
{
  // declare some multi-precision integers
  mpz_t pub_exp, priv_exp, modulus, totient, fac_p, fac_q, next_prime;

  mpz_init_set_str(pub_exp,"5",10);
  mpz_init_set_str(modulus,"10142789312725007",10);

  mpz_init(priv_exp);
  mpz_init(totient);
  mpz_init(fac_p);
  mpz_init(fac_q);

  // now we factor the modulus (the hard part)
  mpz_init(next_prime);
  mpz_sqrt(next_prime,modulus);
  unsigned long removed=0;
  while(!removed)
  {
    mpz_nextprime(next_prime,next_prime);
    removed=mpz_remove(fac_p,modulus,next_prime);
  }

  mpz_remove(fac_q,modulus,fac_p);
  // we now have p and q

  // the totient is (p-1)*(q-1)  
  mpz_t psub, qsub;
  mpz_init(psub);
  mpz_init(qsub);

  mpz_sub_ui(psub,fac_p,1);
  mpz_sub_ui(qsub,fac_q,1);
  mpz_mul(totient,psub,qsub);

  // inverse of the public key, mod the totient..
  mpz_invert(priv_exp,pub_exp,totient);

  gmp_printf("private exponent:\n%Zd\n",priv_exp);

}

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

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

Answer 11

تحتاج إلى عوامل المعامل ، هذه هي المعلمة الأولى للمفتاح العام ، 10142789312725007. ستفعل القوة الغاشمة (تحقق من كل رقم فردي من 3 إلى SQRT (N) إذا كان عاملًا) ، على الرغم من وجود خوارزميات أكثر تطوراً/سريعة.

نظرًا لأن الرقم أكبر من أن يتناسب مع عدد صحيح تقليدي (حتى 64 بت) ، فقد ترغب في مكتبة رقمية تدعم الأعداد الصحيحة للخلايا التعسفية. بالنسبة لـ C ، يوجد GMP و MIPR (أكثر ملاءمة للنظام النووي). ل PHP ، هناك bignum. يأتي Python مع واحد مدمج-نوع بيانات عدد صحيح مدمج بالفعل طول تعسفي.

Answer 12

هناك الكثير من التكهنات السيئة حول عوامل الأعداد الأولية شبه الكبيرة التي تدخل في القوة الغاشمة أو عدم وجود أي منهما لا يلزم عوامله في شبه الذروة. 64 بت تستغرق 1 - 2 ثانية على جهاز الكمبيوتر الخاص بي ، و 256 بت أقل من يومين عموما