Effiziente Exponentiation scheitert?!

eintopf
Mausschubser
Mausschubser
Beiträge: 67
Registriert: 25. Aug 2011 17:41

Effiziente Exponentiation scheitert?!

Beitrag von eintopf »

Hallo,

bearbeite momentan folgende Aufgabe:
Sei m = 12, h(m) = 21. Der private Schlüssel ist (e, n) = (27,55). Gebe eine gültige Signatur an.

Die Signatur sollte ja nun \(s = 21^{27} mod 55\) sein. Nun wollte ich das ganze mit der effizienten Exponentiation rechnen:

Initial: r = 1; b = 21; y = \(11011_2\)
Erster Schritt:
r = r * b = 21
b = (21 * 21) mod 55 = 1
Zweiter Schritt:
r = r * b = 21
b = 1
usw. (r und b ändern sich nicht mehr)

Wo liegt der Fehler? Gibt es eine "Ausnahmebehandlung" wenn b = 1 wird?

Viele Grüße!

plo1234
BASIC-Programmierer
BASIC-Programmierer
Beiträge: 116
Registriert: 14. Nov 2009 18:51

Re: Effiziente Exponentiation scheitert?!

Beitrag von plo1234 »

Hast du \(s = 21^{27} mod 55\) denn mal ausgerechnet? ;)

eintopf
Mausschubser
Mausschubser
Beiträge: 67
Registriert: 25. Aug 2011 17:41

Re: Effiziente Exponentiation scheitert?!

Beitrag von eintopf »

Mein Taschenrechner versagt und mein PC sagt 3 (!= 21)

plo1234
BASIC-Programmierer
BASIC-Programmierer
Beiträge: 116
Registriert: 14. Nov 2009 18:51

Re: Effiziente Exponentiation scheitert?!

Beitrag von plo1234 »

Also meiner sagt

Code: Alles auswählen

In [4]: (21**27) % 55
Out[4]: 21L
edit: http://www.wolframalpha.com/input/?i=21%5E27+mod+55

ElGamal
Nichts ist wie es scheint
Beiträge: 23
Registriert: 19. Dez 2011 20:56

Re: Effiziente Exponentiation scheitert?!

Beitrag von ElGamal »

Ich denke da ist gar kein Fehler :lol:
21 sollte stimmen :!: :wink:

eintopf
Mausschubser
Mausschubser
Beiträge: 67
Registriert: 25. Aug 2011 17:41

Re: Effiziente Exponentiation scheitert?!

Beitrag von eintopf »

ok, werde meinen PC entsorgen. Danke euch =)

Woyzeck
Erstie
Erstie
Beiträge: 18
Registriert: 13. Mär 2011 15:30

Re: Effiziente Exponentiation scheitert?!

Beitrag von Woyzeck »

@ eintopf: weiß nicht, ob du dich vielleicht nur vertippt hast, aber einen privaten Schlüssel (n, e) gibt es nicht. Das wäre der öffentliche.

Signieren tut man ja mit d -> dem privaten Schlüssel.

Ergo müsstest du, wenn die Aufgabe tatsächlich so lautet, wie geschrieben, zuerst das inverse zu e bestimmen in Z_40 (phi(55)=40). Das ist 3 und die Aufgabe wird wesentlich leichter.

Antworten

Zurück zu „Archiv“