| Autor |
Nachricht |
VeryApe
Anmeldungsdatum: 10.02.2008
Beiträge: 3247
|
 VeryApe Verfasst am: 01. März 2024 23:34 Titel: Modulo Rechnung |
 |
|
Hallo, die Frage wäre eigentlich fürs matheboard, aber ich bin dort kein Mitglied, aber in Physik sind eh alle mathematisch fit.
Ich beschäftige mich momentan mit x509 Verschlüsselungszertifikaten, also die PEM wrapper files bei HTTPS RSA in ASN.1 DER . Manuell mal so ne Signatur überprüfen mit öffentlichen Schlüssel, herumrechnen halt.
Dabei hatte ich mir jetzt grundsätzliche Fragen zur Modulo Rechnung, also Restwert Rechnung gestellt.
Wenn ich  rechne, dann ist es ziemlich eindeutig, dass für x=0 und x=m der Restwert 0 ist, dabei stellte sich mir die Frage, ob es nicht Werte für x gibt  , bei denen auch der Restwert 0 ist.
z.B. m=20, x=10, i=3 => Restwert 0 , wäre so ein Beispiel
Das kann ich ausschließen, wenn m eine Primzahl ist, über einen einfachen Beweis, den wahrscheinlich eh jeder kennt, der darauf führt-> das Produkt zweier Zahlen ist nur dann durch eine Primzahl teilbar, wenn eine der Zahlen durch dieser Primzahl teilbar ist.
wenn m das Produkt zweier Primzahlen ist  mußte ich mir erst beweisen, dass wenn eine ganze Zahl x durch eine Zahl y nicht restlos dividiert werden kann, kann dann auch das Ergebnis durch eine weitere Zahl z nicht restlos dividiert werden. also so->
 qy... ganze Zahl bei Divison durch y, Ry ... Rest, gilt dann auch  hat definitiv einen Rest?
Beweis:
 q_z ... ganze Zahl bei division durch z
Es gilt  , wenn Rz=0 bleibt 
wenn nicht:
 , Rz kann nur maximal z-1 sein
*y+R_{y}}{yz} => \frac{x}{yz}=q_{z}+\frac{yz-y+R_{y}}{yz} ) Ry kann maximal y-1 sein, damit fehlt mindestens  auf eine ganze Zahl, nur als Beispiel.
Jetzt konnt ich mir zeigen. dass es zwischen  für jedes x sicher einen Restwert gibt.
weiters kann ich mir eine Symmetrie beweisen, dass ^{i} \mod m = m-a ) ist.
Ich scheitere aber an einem Beweis, das zwar jedes x einen Restwert hat, dieser aber für jedes x unterschiedlich ist. Ich weiß nur, wenn zwei verschiedene Zahlen den gleichen Restwert haben dann gilt:
 \mod m =0) ___  und sollte dies der Fall sein
dann kann  keine ganze Zahl sein. Alle Beweise sind nur für ganze Zahlen gültig.
Wie kann man das beweisen? |
|
 |
TomS
Moderator
Anmeldungsdatum: 20.03.2009
Beiträge: 18089
|
| TomS Verfasst am: 02. März 2024 00:59 Titel: |
|
|
Der Trick besteht darin, x mittels eines geeignetem p zu zerlegen als
Dann gilt.
 \, x^{i-1} \, \text{mod} \, m = a \, x^{i-1} \, \text{mod} \, m )
Aber das funktioniert natürlich für jeden Faktor, also
Etwas komplizierter wird es dann im nächsten Schritt, sowie bereits im ersten, wenn x < m. Man gruppiert die Potenzen so, dass
^k \, a^\nu = (b + qm)^k \, a^\nu)
und damit natürlich
^k \, a^\nu \, \text{mod} \, m = b^k \, a^\nu \, \text{mod} \, m )
usf.
Dabei sind alle Zahlen positiv und ganzzahlig.
_________________
Niels Bohr brainwashed a whole generation of theorists into thinking that the job (interpreting quantum theory) was done 50 years ago. |
|
|
VeryApe
Anmeldungsdatum: 10.02.2008
Beiträge: 3247
|
| VeryApe Verfasst am: 03. März 2024 00:16 Titel: |
|
|
ahoi TomS,
| TomS hat Folgendes geschrieben: | Der Trick besteht darin, x mittels eines geeignetem p zu zerlegen als
|
hm, das funktioniert aber gerade für x < m nicht, dann ist a=x.
das hatte ich auch schon, das führte mich auf einen Beweis das
^{i} \mod m = (m*n+x)^{i} \mod m) ist.
m*n... Vielfache von m, n=0 bis ganzzahlig unendlich
das führt auf eine sich wiederholende Kette, sei m=6, x<m,
Restwerte
Der Rest deines Kommentars, da bist du glaube ich schon einen Schritt weiter als ich.
Vielleicht nochmal: konkretes Beispiel , RSA , niedrige Zahlen, durchschaubar halt
Man nehme zwei Primzahlen: 
dann ist der Modulus: 
(mit den obigen Beweis ist damit schon mal sicher, dass es für alle x (0<x<m) einen Restwert gibt)
Jetzt errechne man: =(P1-1)*(P2-1)=60)
Man wähle einen ungeraden zu ) teilerfremden Exponenten e für den gilt -1) : 
Nun errechne man den zweiten Exponenten d so, dass  \mod \varphi(N)=1) ergibt.
(ungerade Exponenten deswegen, weil man sonst bei der Multiplikation beider Exponenten durch eine gerade Zahl nie einen Restwert von 1 hätte. ist immer gerade.)
nach ein bischen rechnen  ,  \mod 120 = 1)
damit habe ich:
PUBLIC KEY: Exponent e=7, Modulus: N=77
PRIVATE KEY: Exponent d=43, Modulus: N=77
Eine Zahl verschlüssle ich nun wie folgt, Z=unverschlüsselte Zahl, Z'=verschlüsselte Zahl, Z=60
Verschlüsselung PUBLIC KEY: 
Entschlüsselung PRIVATE KEY: 
oder umgekehrt Signatur:
Verschlüsselung PRIVATE KEY: 
Entschlüsselung PUBLIC KEY: 
Aufgrund der sich wiederholenden Restwerte Kette, kann ich nur Zahlen von 1 bis 76 verschlüsseln, denn 0 und 77 ergeben Restwert 0, 77+1 und 1 ergeben den selben Restwert, 77+2 und 2 ergeben den selben Restwert, usw
Dann hätte ich eine Mehrdeutigkeit und könnte den Ursprung nicht wiederherstellen.
und jetzt kommt der eigentliche Punkt, den ich mir als nächsten Schritt beweisen will.
Jetzt weiß ich, dass jedes x , 0<x<m sicher einen Restwert hat. Es muß aber sicher gestellt sein, dass jedes x auch einen unterschiedlichen Restwert hat, denn sonst hätte ich auch innerhalb 0<x<m eine Mehrdeutigkeit drinnen, wenn zwei verschiedene x denselben Restwert ergeben!
Jetzt schüttle ich aber einfach so einen ungeraden Exponenten aus den Handgelenk -> den kann ich ja frei wählen und weiß gar nicht, ob der mit den angenommen Modulus sicher ist.
dazu habe ich mir ein Script für die Browser Console geschrieben, dass die Restwerte, bei verschiedenen Exponenten i anzeigt.
 => i entspricht e, m entspricht N
_x │ 01 02 03 04 05 06 07 08 09 10
──┼───────────────────────────────
00 │ 01 51 31 60 47 41 28 57 37 10
10 │ 11 12 62 42 71 58 52 39 68 48
20 │ 21 22 23 73 53 05 69 63 50 02
30 │ 59 32 33 34 07 64 16 03 74 61
40 │ 13 70 43 44 45 18 75 27 14 08
50 │ 72 24 04 54 55 56 29 09 38 25
60 │ 19 06 35 15 65 66 67 40 20 49
70 │ 36 30 17 46 26 76
unique complete residual values!
--------------------------------------------------------------------
 => i entspricht e, m entspricht N
_x │ 01 02 03 04 05 06 07 08 09 10
──┼───────────────────────────────
00 │ 01 57 69 15 27 06 07 08 64 76
10 │ 22 34 13 14 15 71 06 29 41 20
20 │ 21 22 01 13 36 48 27 28 29 08
30 │ 20 43 55 34 35 36 15 27 50 62
40 │ 41 42 43 22 34 57 69 48 49 50
50 │ 29 41 64 76 55 56 57 36 48 71
60 │ 06 62 63 64 43 55 01 13 69 70
70 │ 71 50 62 08 20 76
1: multiples at x 1, 23, 67
6: multiples at x 6, 17, 61
8: multiples at x 8, 30, 74
13: multiples at x 13, 24, 68
15: multiples at x 4, 15, 37
20: multiples at x 20, 31, 75
22: multiples at x 11, 22, 44
27: multiples at x 5, 27, 38
29: multiples at x 18, 29, 51
34: multiples at x 12, 34, 45
36: multiples at x 25, 36, 58
41: multiples at x 19, 41, 52
43: multiples at x 32, 43, 65
48: multiples at x 26, 48, 59
50: multiples at x 39, 50, 72
55: multiples at x 33, 55, 66
57: multiples at x 2, 46, 57
62: multiples at x 40, 62, 73
64: multiples at x 9, 53, 64
69: multiples at x 3, 47, 69
71: multiples at x 16, 60, 71
76: multiples at x 10, 54, 76
not found: 2, 3, 4, 5, 9, 10, 11, 12, 16, 17, 18, 19, 23, 24, 25, 26, 30, 31, 32, 33, 37, 38, 39, 40, 44, 45, 46, 47, 51, 52, 53, 54, 58, 59, 60, 61, 65, 66, 67, 68, 72, 73, 74, 75,
---------------------------------------------------------
 => i entspricht e, m entspricht N
_x │ 01 02 03 04 05 06 07 08 09 10
──┼───────────────────────────────
00 │ 01 65 45 67 12 76 21 43 23 10
10 │ 11 12 76 56 01 23 10 32 54 34
20 │ 21 22 23 10 67 12 34 21 43 65
30 │ 45 32 33 34 21 01 23 45 32 54
40 │ 76 56 43 44 45 32 12 34 56 43
50 │ 65 10 67 54 55 56 43 23 45 67
60 │ 54 76 21 01 65 66 67 54 34 56
70 │ 01 65 10 32 12 76
1: multiples at x 1, 15, 36, 64, 71
10: multiples at x 10, 17, 24, 52, 73
12: multiples at x 5, 12, 26, 47, 75
21: multiples at x 7, 21, 28, 35, 63
23: multiples at x 9, 16, 23, 37, 58
32: multiples at x 18, 32, 39, 46, 74
34: multiples at x 20, 27, 34, 48, 69
43: multiples at x 8, 29, 43, 50, 57
45: multiples at x 3, 31, 38, 45, 59
54: multiples at x 19, 40, 54, 61, 68
56: multiples at x 14, 42, 49, 56, 70
65: multiples at x 2, 30, 51, 65, 72
67: multiples at x 4, 25, 53, 60, 67
76: multiples at x 6, 13, 41, 62, 76
not found: 2, 3, 4, 5, 6, 7, 8, 9, 13, 14, 15, 16, 17, 18, 19, 20, 24, 25, 26, 27, 28, 29, 30, 31, 35, 36, 37, 38, 39, 40, 41, 42, 46, 47, 48, 49, 50, 51, 52, 53, 57, 58, 59, 60, 61, 62, 63, 64, 68, 69, 70, 71, 72, 73, 74, 75,
Wie kann ich beweisen, dass dies bei großen Exponenten und hohen Modulo Zahlen nicht der Fall ist?
Ich denke schon die ganze Zeit darüber nach.
hier das Script für die CONSOLE -> STRG+SHIFT+J, m und i kann man ändern
ein angehängtes n an der Zahl bedeutet in Javascript einen BigInteger
| Zitat: |
var columns=10,
m=7n*11n, // -- modulo P1*P2
i=25n, // -- exponent -> x^i % m , 0 < x < m
i_bits=i.toString(2), // m ... modul i_bits=i.toString(2), // m ... modul^o
x, xx, R, R_int, j, RsX_Collector=[], line="\u2500\u2500\u2500\u253C", RsXcheck="", notFound="not found: ", multiples="";
//-- building head
output="x \u2502 ";
for (j=0;j<columns;j++) output+=(j+1).toString().padStart(2,"+")+" ";
output=output.slice(0,-1)+"\n"+line.padEnd(output.length,"\u2500")+"\n"; line="";
for (x=1;x<m;x++)
{
R=1n; xx=BigInt(x);
for (j=i_bits.length-1;j>-1;j--)
{
if (i_bits.charAt(j)=="1") R*=xx;
if (i!=0) xx*=xx%m
}
R=R%m; R_int=Number(R);
if (RsX_Collector[R_int] === undefined) RsX_Collector[R_int]=x;
else RsX_Collector[R_int]+=", "+x;
line+=R_int.toString().padStart(2,"0")+" ";
if (x%columns==0)
{
output+=((x-columns)+" \u2502 ").toString().padStart(5,"0")+line.slice(0,-1)+"\n";
line="";
}
}
output+=((x-x%columns)+" \u2502 ").toString().padStart(5,"0")+line.slice(0,-1)+"\n";
for (j=1;j<m;j++)
{
if (RsX_Collector[j] == undefined) notFound+=" "+j+",";
else { if (RsX_Collector[j].length>3) multiples+=j+": multiples at x "+RsX_Collector[j]+"\n";}
}
if (!multiples) RsXcheck="unique complete residual values!"
else RsXcheck=multiples+"\n"+notFound;
console.log (output);
console.log (RsXcheck);
|
hm, ich werde die ganze Zeit ausgeloggt, obwohl ich immer auf Vorschau klicke, Textgrafik wird auch keine unterstützt, weil die Schriftart variable Schriftbreite hat. hm.
_________________
WAS IST LOS IN EUROPA? https://www.youtube.com/watch?v=a9mduhSSC5w
Zuletzt bearbeitet von VeryApe am 03. März 2024 11:22, insgesamt einmal bearbeitet |
|
|
TomS
Moderator
Anmeldungsdatum: 20.03.2009
Beiträge: 18089
|
| TomS Verfasst am: 03. März 2024 07:09 Titel: |
|
|
Ich versuche das mal für mich zusammenzufassen.
RSA
 = \Big| \{a\in \mathbb {N} \,\mid \,1\leq a\leq n \,\land\, \gcd(a,n)=1\} \Big| )
hier speziell
=(p-1)\cdot (q-1))
wähle i, so dass
 - 1 \,\land\, \gcd(\Phi, i)=1 )
berechne j, so dass
)
public und private Key (i, N) und (j, N)
Ver- und Entschlüsseln:
Soweit alles klar und deine Zahlenbeispiele für 7 und 11 verstehe ich. Dein anschließendes Problem verstehe ich nicht.
Außerdem habe ich mir nochmal die englische Wikipedia durchgelesen, und ich sehe nicht unmittelbar, dass das übereinstimmt:
https://en.wikipedia.org/wiki/RSA_(cryptosystem)#Key_generation
| Zitat: | | Compute λ(n), where λ is Carmichael's totient function |
_________________
Niels Bohr brainwashed a whole generation of theorists into thinking that the job (interpreting quantum theory) was done 50 years ago. |
|
|
VeryApe
Anmeldungsdatum: 10.02.2008
Beiträge: 3247
|
| VeryApe Verfasst am: 03. März 2024 11:09 Titel: |
|
|
Als einfacher Depp, ders nicht so mit mathematischen Schreibweisen hat, habe ich mich an das gehalten.
| https://de.wikipedia.org/wiki/RSA-Kryptosystem hat Folgendes geschrieben: |
Erzeugung des öffentlichen und privaten Schlüssels
Die Schlüssel bestehen aus den drei Zahlen e , d {\displaystyle e,d} und N {\displaystyle N}. Man nennt N {\displaystyle N} den RSA-Modul, e {\displaystyle e} den Verschlüsselungsexponenten und d {\displaystyle d} den Entschlüsselungsexponenten. Das Zahlenpaar ( e , N ) {\displaystyle (e,N)} bildet den öffentlichen Schlüssel (public key) und das Paar ( d , N ) {\displaystyle (d,N)} den privaten Schlüssel (private key). Diese Zahlen werden durch das folgende Verfahren erzeugt:
Wähle zufällig und stochastisch unabhängig zwei Primzahlen p ≠ q {\displaystyle p\neq q}. Diese sollen die gleiche Größenordnung haben, aber nicht zu dicht beieinander liegen, sodass der folgende Rahmen ungefähr eingehalten wird: 0 , 1 < | log 2 p − log 2 q | < 30 {\displaystyle 0{,}1<|\log _{2}p-\log _{2}q|<30}.[6] (In der Praxis erzeugt man dazu solange Zahlen der gewünschten Länge und führt mit diesen anschließend einen Primzahltest durch, bis man zwei Primzahlen gefunden hat.)
Berechne den RSA-Modul
N = p ⋅ q {\displaystyle N=p\cdot q}
Berechne die Eulersche φ-Funktion von N {\displaystyle N}
φ ( N ) = ( p − 1 ) ⋅ ( q − 1 ) {\displaystyle \varphi (N)=(p-1)\cdot (q-1)}
Wähle eine zu φ ( N ) {\displaystyle \varphi (N)} teilerfremde Zahl e {\displaystyle e}, für die gilt 1 < e < φ ( N ) − 1 {\displaystyle 1<e<\varphi (N)-1}.
Berechne den Entschlüsselungsexponenten d {\displaystyle d} als multiplikativ Inverses von e {\displaystyle e} bezüglich des Moduls φ ( N ) {\displaystyle \varphi (N)}, was mit dem erweiterten euklidischen Algorithmus erfolgen kann. Es soll also die Kongruenz gelten:
e ⋅ d ≡ 1 ( mod φ ( N ) ) {\displaystyle e\cdot d\equiv 1{\pmod {\varphi (N)}}} |
dabei habe ich wohl was vergessen
| veryape hat Folgendes geschrieben: | | Man wähle eine ungeraden Exponenten i: |
Der Exponent muß nicht nur ungerade sein, sondern auch teilerfremd und es muß gültig sein.
-1 )
Ich werde es oben ausbessern und benutze die Variabeln wie im Text von wikipedia
_________________
WAS IST LOS IN EUROPA? https://www.youtube.com/watch?v=a9mduhSSC5w |
|
|
VeryApe
Anmeldungsdatum: 10.02.2008
Beiträge: 3247
|
| VeryApe Verfasst am: 03. März 2024 11:51 Titel: |
|
|
Also folgendes, mein gewählter Exponent e=7 ist erlaubt., der Modulus N sei 77.
Angenommen ich würde die Zahlen 60 und 137 verschlüsseln , dann ist 137=(N+60)
dann würde ja gültig sein: ^{e} \mod N)
Dann wüsste ich ja bei der Entschlüsselung nicht, ob ich die Zahl 60 oder 137 verschlüsselt hätte. also kann ich nur Zahlen 0<Z<77 verschlüsseln, wobei 1 und 76 eigentlich auch keinen Sinn machen, weil 1 ergibt Rest 1, und 76 ergbit immer 76. Die ergeben also verschlüsselt immer dasselbe , wie entschlüsselt.
Jetzt mal angenommen ich würde e=21 wählen, sei dahingestellt, ob ich es darf oder nicht.
Tabelle (siehe oben) i=21 m=77 => i entspricht e, m entspricht N
Restwert 13: multiples at x 13, 24, 68
Z sei 0<Z<N = 13, 24, 68
Dann wüsste ich nach der Verschlüsselung nicht mehr, ob ich 13, 24, 68 verschlüsselt hätte. dann wäre auch für Z 0<Z<N nicht sicher, ob ich den Ursprung wieder herstellen könnte.
Wie kann ich nun sicher sein, das dies bei erlaubten Exponenten nicht der Fall ist.
Es läuft wahrscheinlich darauf hinaus zu beweisen warum
ich die Exponenten e, d so wählen muß das:
e zu teilerfremd ist und
und für d gilt:
denn ich habe mir die Restwert Tabellen für alle erlaubten Exponenten e <77 angesehen und, da kommen keine multiple Restwerte vor, jeder Restwert kommt nur einmalig vor, wieso ist das so? hm, ich muß nochmal drüber nachdenken.
_________________
WAS IST LOS IN EUROPA? https://www.youtube.com/watch?v=a9mduhSSC5w |
|
|
TomS
Moderator
Anmeldungsdatum: 20.03.2009
Beiträge: 18089
|
| TomS Verfasst am: 03. März 2024 12:12 Titel: |
|
|
Ich glaube, es läuft wirklich nur darauf hinaus, was ich oben geschrieben habe:
Mit
gilt
Also existiert eine obere Schranke
oberhalb der nicht mehr verschlüsselt werden darf, da sonst
D.h. die Funktion wäre nicht bijektiv, d.h. nicht eindeutig umkehrbar. Ja, das ist sicher so.
Gefühlt würde ich sagen, man muss sicherstellen, dass auch die Reste groß sein sollen, also z weit weg von 1 und m sein sollte. Aber das findest du sicher irgendwo.
Praktisch ist das alles nicht schlimm, da man RSA nicht zum Verschlüsseln der Nachricht selbst sondern zum Verschlüsseln eines Keys für eine symmetrische Verschlüsselung verwendet, wobei man die Nachricht konventionell verschlüsselt und dem mit RSA verschlüsselten mit der Nachricht zusammen verschicken kann.
_________________
Niels Bohr brainwashed a whole generation of theorists into thinking that the job (interpreting quantum theory) was done 50 years ago. |
|
|
|
|
Registrieren
Login
FAQ
Suchen
