Aufgabe 4
-
- Beiträge: 225
- Registriert: Sa 25. Okt 2008, 12:48
Aufgabe 4
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.
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.
Re: Aufgabe 4
btw: habe gerade gesehen, dass sich die zu entschlüsselnde Nachricht geändert hat
-
- Beiträge: 225
- Registriert: Sa 25. Okt 2008, 12:48
Re: Aufgabe 4
http://www.cs.princeton.edu/introcs/78c ... .java.html
Ist der Link, das geänderte Codewort behebt nur einen Rechtschreibfehler.
Ist der Link, das geänderte Codewort behebt nur einen Rechtschreibfehler.
Re: Aufgabe 4
verschlusseln Nachrichte ist 55166353023336718628437059069325451331624304236823354133219782674
d= 78873580590140196878733625930448702465747065315080575901346908059
Nachrichte ist "fortes fortuna adiuvat"
Ist meine Loesung richtig?
d= 78873580590140196878733625930448702465747065315080575901346908059
Nachrichte ist "fortes fortuna adiuvat"
Ist meine Loesung richtig?
Re: Aufgabe 4
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.
Brute force scheint wohl keine gute Lösung zu sein.
Wie berechnet man das?
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);
Wie berechnet man das?
Re: Aufgabe 4
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);
}
Re: Aufgabe 4
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.
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.
-
- Beiträge: 225
- Registriert: Sa 25. Okt 2008, 12:48
Re: Aufgabe 4
Theoretisch mit dem Square and Multiply-Algorithmus, aber da die Zahlen so riesig und langwierig sind wird da afaik nur die Lösung verlangt.salami hat geschrieben: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.
-
- Beiträge: 225
- Registriert: Sa 25. Okt 2008, 12:48
Re: Aufgabe 4
Komme auf eine andere Verschlüsselung. Rechnest du auchkukugo hat geschrieben:verschlusseln Nachrichte ist 55166353023336718628437059069325451331624304236823354133219782674
d= 78873580590140196878733625930448702465747065315080575901346908059
Nachrichte ist "fortes fortuna adiuvat"
Ist meine Loesung richtig?
Code: Alles auswählen
String result = rsaone(new BigInteger("18151301140927092005270415132113"), e, N).toString();
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);
}
}
Re: Aufgabe 4
Meine Ergebnisse:
Ich hoffe nur, dass es tatsächlich ausreicht, einfach die Antworten anzugeben... Ich beneide aber unsere Tutoren nicht, die das überprüfen sollen
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"
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"
When we say that two functions are almost always used together, we should remember that "almost" is a euphemism for "not."
-- David L. Parnas, "Designing Software for Ease of Extension and Contraction"
-- David L. Parnas, "Designing Software for Ease of Extension and Contraction"