Aufgabe 4

[Christian S.]

Hallo,
Hat jemand einen Link zu einem Programm, mit dem man diese riesigen Potenzen /modulos ausrechnen kann? Ich habe versucht mir selbst was mit dem square and multiply algorithmus zu basteln, bin aber kläglich gescheitert .
Edit: Hat sich erledigt, habe was gefunden, was ich leicht geändert in Java implementiert habe.

[Tobias]

btw: habe gerade gesehen, dass sich die zu entschlüsselnde Nachricht geändert hat

[Christian S.]

http://www.cs.princeton.edu/introcs/78c ... .java.html
Ist der Link, das geänderte Codewort behebt nur einen Rechtschreibfehler.

[kukugo]

verschlusseln Nachrichte ist 55166353023336718628437059069325451331624304236823354133219782674
d= 78873580590140196878733625930448702465747065315080575901346908059
Nachrichte ist "fortes fortuna adiuvat"
Ist meine Loesung richtig?

[salami]

Hallo, kann mir jemand erklären, wie man d berechnet?

Habe jetzt seit 10 Minuten das folgende laufen, aber ich vermute, da kann ich noch lange warten.
Besonders, wenn ich bei kukugo sehe, wie groß die Zahl ist.

Code: Alles auswählen

		BigInteger d = new BigInteger("1");
		while ((e.multiply(d)).mod(phiN) != BigInteger.ONE) {
			d = d.add(BigInteger.ONE);
		}
		
		System.out.println(d);

Brute force scheint wohl keine gute Lösung zu sein.
Wie berechnet man das?

[kukugo]

Code: Alles auswählen

public class RSA {
   private final static BigInteger one      = new BigInteger("1");
   private final static SecureRandom random = new SecureRandom();

   private BigInteger privateKey;
   private BigInteger publicKey;
   private BigInteger modulus;

   // generate an N-bit (roughly) public and private key
   RSA(int N) {
      BigInteger p = new BigInteger("100000000000000000000000000000049");
      BigInteger q = new BigInteger("1000000000000000000000000000000061");
      BigInteger phi = (p.subtract(one)).multiply(q.subtract(one));

      modulus    = p.multiply(q);                                  
      publicKey  = new BigInteger("10000000019");     // common value in practice = 2^16 + 1
      privateKey = publicKey.modInverse(phi);
   }


   BigInteger encrypt(BigInteger message) {
      return message.modPow(publicKey, modulus);
   }

Ich habe die Code so geaendert.die entsprechend eingabe habe ich auch einbissen aendert.

[salami]

Ah vielen Dank,
BigInteger d = e.modInverse(phiN);
war das was ich gesucht habe.

Jetzt müsste man noch rausfinden, wie man das manuell berechnet, damit mans irgendwie als Lösung aufschreiben kann.

[Christian S.]

Ah vielen Dank,
BigInteger d = e.modInverse(phiN);
war das was ich gesucht habe.

Jetzt müsste man noch rausfinden, wie man das manuell berechnet, damit mans irgendwie als Lösung aufschreiben kann.

Theoretisch mit dem Square and Multiply-Algorithmus, aber da die Zahlen so riesig und langwierig sind wird da afaik nur die Lösung verlangt.

[Christian S.]

verschlusseln Nachrichte ist 55166353023336718628437059069325451331624304236823354133219782674
d= 78873580590140196878733625930448702465747065315080575901346908059
Nachrichte ist "fortes fortuna adiuvat"
Ist meine Loesung richtig?

Komme auf eine andere Verschlüsselung. Rechnest du auch

Code: Alles auswählen

String result = rsaone(new BigInteger("18151301140927092005270415132113"), e, N).toString();

Oder habe ich da womöglich was vertauscht ^^?
Edit: gerade nochmal überprüft, der Code, den ich nutze, lautet:

Code: Alles auswählen

import java.math.BigInteger;
import java.security.SecureRandom;
class Rsa {
  static BigInteger ONE = new BigInteger("1");
  static BigInteger p = new BigInteger("100000000000000000000000000000049");
  static BigInteger q = new BigInteger("1000000000000000000000000000000061");
  static BigInteger phi = (p.subtract(ONE)).multiply(q.subtract(ONE));
  static BigInteger N = p.multiply(q);
  static BigInteger e = new BigInteger("10000000019");
  static BigInteger d = e.modInverse(phi);

  static BigInteger rsaone(BigInteger a, BigInteger b, BigInteger N) {
    return a.modPow(b, N);
  }

  public static void main(String [ ] args) {
    String result = rsaone(new BigInteger("18151301140927092005270415132113"), e, N).toString();
    Terminal.println(result);
    Terminal.println(d.toString());
    String resultTwo = rsaone(new BigInteger("98715851081927302955293144920226883853370114478144536812943055746"), d, N).toString();
    Terminal.println(resultTwo);
  }
}

[SLS]

Meine Ergebnisse:

PRIME_BBCODE_SPOILER_SHOW PRIME_BBCODE_SPOILER: auf Anzeigen klicken

(i)
Alphabetcodiert: 18151301140927092005270415132113 (stimmt mit dem Ergebnis von "Christian S." überein)
RSA-verschlüsselt: 17502712952585122157418603047178562651163505295924481547515758527 (entschlüsseln mit dem 'd' unten ergibt tatsächlich das erwartete)

(ii)
d = 78873580590140196878733625930448702465747065315080575901346908059
"fortes fortuna adiuvat"

Ich hoffe nur, dass es tatsächlich ausreicht, einfach die Antworten anzugeben... Ich beneide aber unsere Tutoren nicht, die das überprüfen sollen