Diffie-Hellman Riss mit Teilinfo bekannt

Question

Das ist Schularbeit.

Ich habe das Problem, die privaten Schlüssel beider Parteien in einer DH-Exchange zu finden. Die an den Tests beteiligten Zahlen sind nicht groß genug und die Aufgabe ist im Grunde Brute-Force. In der Aufgabe kann ich die prime , Generator g und Alices öffentlichen Schlüssel A bekommen. Ich habe auch die Methoden zum Verschlüsseln einer Nachricht und entschlüsseln eine Nachricht mit einem benutzerdefinierten Schlüssel.

Im Moment habe ich nur a durch einfaches Durchschleifen ganzer Zahlen i=1...p bekommen und überprüft, ob g^i mod p == g^A mod p und prompt den ersten Wert zurückgibt, der die Anforderung erfüllt.

Allerdings ist meine Lösung nicht immer nach automatisierten Tests wahr. Wer weiß, wie oder sogar, wenn es möglich ist, a und b Flossen mit den gegebenen Informationen?

Answer 1

Dank eines Dritten, gelang es mir, den DH-Code zu knacken:

public Integer crackAlice() { 
     // TODO 
     Integer alicePrivate = 0; 

     int p = session.getP(); 
     int g = session.getG(); 
     int A = session.getAlicesPublicKey(); 
     // A = g^a mod p 


     System.out.println("Alice public A: "+A); 
     String message = String.valueOf(156215); 

     for (int i = 1; i < p; i++) { 
      if (BigInteger.valueOf(g).pow(i).mod(BigInteger.valueOf(p)).equals(BigInteger.valueOf(A))) { 
       //System.out.println("\t\t\t\t"+BigInteger.valueOf(g).pow(i)); 
       alicePrivate = i; 
       System.out.println("Potential Alice private a: "+i); 
       //break; 
      } 
     } 
     return alicePrivate; 
    } 

und

public Integer crackBob() { 
     // TODO 

     Integer bobPrivate = 0; 
     Integer a = crackAlice(); 
     int p = session.getP(); 
     int g = session.getG(); 
     int A = session.getAlicesPublicKey(); 
     String mainMessage = "teade"; 

     String msg = null; 
     try { 
      msg = session.getEncrypted(mainMessage); 
     } catch (Exception e) { 
      e.printStackTrace(); 
     } 

     for (int i = 1; i < p; i++) { 
      int ai = a*i; 
      int Ai = A*i; 
      //System.out.println("a*b = "+ai); 
      BigInteger bigintP = BigInteger.valueOf(p); 
      if (((BigInteger.valueOf(g).pow(a).mod(bigintP)).pow(i)).mod(bigintP) 
        .equals(((BigInteger.valueOf(g).pow(i).mod(bigintP)).pow(a)).mod(bigintP))) { 
       String decrypt = null; 
       try { 
        decrypt = session.getDecryptedWithCustomKey(msg, BigInteger.valueOf(g).pow(a*i).mod(bigintP).intValue()); 
       } catch (Exception e) { 
        e.printStackTrace(); 
       } 
       if (decrypt != null && decrypt.trim().equals(mainMessage)) { 
        bobPrivate = i; 
        break; 
       } 
      } 
     } 
     return bobPrivate; 
    } 

Ich hoffe, das andere helfen mit einem ähnlichen Problem heraus.