Как быстро сломать шифрование RSA с очень большими числами в Java с помощью ключа Modulus and Exponent / Publi c - PullRequest
Новая
       16

Как быстро сломать шифрование RSA с очень большими числами в Java с помощью ключа Modulus and Exponent / Publi c

2 голосов
/ 30 марта 2020

Мне было поручено создать программу, которая взломала бы шифрование RSA с помощью модуля и открытых ключей c обеих сторон и зашифрованного текста. Я нашел решения, которые грубой силой находят простые значения, которые умножаются на модуль. Однако с размером чисел, которые я должен использовать, не похоже, что он может даже завершить sh обработку (модуль длиной 30 цифр или около того)

Это пример данных, которые мы были заданы: 

{
"alice": {
"modulus": "66056083785421544972111685239",
"publicKey": "38933338385103628492607145193"
},
"bob": {
"modulus": "71994651332404115788173195239",
"publicKey": "28763302913765661132800185637"
},
"cipherText": "5b8sot9g2168mp3nw51"
}

Это решение, которое я сейчас пытаюсь, используя алгоритм Ферма, чтобы попытаться найти простые числа быстрее: 

import java.math.BigInteger;
public class ferr
{

    static BigInteger r1;
    static BigInteger r2;
    static BigInteger aliceModulus = new BigInteger("107182711767121947041078387099");

    public static void main (){
        System.out.println("running");
        ferr x = new ferr();
     x.fermat(aliceModulus);
    }


    public void fermat(BigInteger N)
    {
        BigInteger a = calcSQR(N);
        BigInteger b2 = (a.multiply(a).subtract(N));
        while(Square(b2) == false) {
            a = a.add(BigInteger.valueOf(1));
            b2 = (a.multiply(a).subtract(N));
        } // end while
        r1 = a.subtract(calcSQR(b2));
        r2 = N.divide(r1);
        System.out.println("Roots = ("+ r1 +") , ("+ r2 +")");
    }

    public boolean Square(BigInteger N)
    {
        BigInteger sqRoot = calcSQR(N);
        if(sqRoot.multiply(sqRoot).equals(N)) {
            return true;
        } // end if
        else {
            return false;
        } // end else
    }

    public BigInteger calcSQR(BigInteger N)
    {
        if(N == BigInteger.ZERO || N == BigInteger.ONE) {
            return N; 
        } // end if
        BigInteger two = BigInteger.valueOf(2L);
        BigInteger x;
        // Starting with x = N/2 avoids magnitude issues with x squared
        for(x = N.divide(two); x.compareTo(N.divide(x)) > 0; x = ((N.divide(x)).add(x)).divide(two)) {
            if(N.compareTo(x.multiply(x)) == 0) {
                return x;
            } // end if
            else { 
                return x.add(BigInteger.ONE); 
            } // end else
        } // end for-loop
        return null;
    }
}

Есть ли более быстрое решение, чтобы сломать шифрование? Я оставил эту программу запущенной в течение нескольких часов, но до конца ее все еще нет.

1 Ответ

6 голосов
/ 31 марта 2020

Как вы заметили, грубое форсирование простых чисел довольно медленно.
Но есть и более простые способы.

  1. Обратите внимание, что у вас есть два по модулю, один для Боба, один для Алисы.
    Тривиальный выстрел - вычислить наибольший общий делитель: 

    BigInteger bobM = new BigInteger("66056083785421544972111685239");
BigInteger aliceM = new BigInteger("71994651332404115788173195239");
System.out.println(bobM.gcd(aliceM));

    Это выдаст 535006138814359, что является одним из факторов как Боба, так и Алисы.

    Это может быть просто удача, что это работает здесь, или это может быть сделано вашим инструктором.

  2. Используйте более быстрый метод факторизации.

    Один из них Алгоритм Полларда Rho , который довольно легко реализовать. 

    private static BigInteger pollardroh(BigInteger n, BigInteger x) {
    BigInteger y = x;
    BigInteger d = BigInteger.ONE;
    while (d.equals(BigInteger.ONE)) {
        x = x.modPow(BigInteger.TWO, n).add(BigInteger.ONE);
        y = y.modPow(BigInteger.TWO, n).add(BigInteger.ONE);
        y = y.modPow(BigInteger.TWO, n).add(BigInteger.ONE);
        d = x.subtract(y).abs().gcd(n);
    }
    return d;
}

    Используйте его с начальным значением x = BigInteger.TWO. Это будет продолжаться ~ 1 минуту на моей машине и вывести 134567897654321 по модулю Алисы.

В конце приведем факторизацию по модулю Алисы и Боба: 

Bob:
p1: 535006138814359
p2: 123467898764321

Alice:
p1: 535006138814359
p2: 134567897654321

Вторые простые числа выглядят немного подозрительно, а не выбираются случайным образом.

...