Unser Diffie-Helman-Hack Nummer 15145!
\n
Als erstes, kleines Schmankerl stellen wir euch hier ein Programm noch im 10-digit Modus vor, mit dem sich aus den öffentlichen Key-Elementen des klassischen (überholten) Diffie-Helman-Verfahren, dem modulus (hier \"p\") und dem Faktor e der abgeleiteten Zahl phi(p)+1 der andere Faktor von phi(p)+1 berechnen lässt, der für die Entschlüsselung gebraucht wird, sowie phi(p) selbst, damit dann auch (sehr viel leichter) die Faktoren von p.
\n
Zur Erinnerung /Erklärung:
\n
Diffie-Helman ist eine Art Urform des RSA-Algorithmus zur Verschlüsselung von Internetinformationen.
\n
Grundprinzip ist die Verteilung des Codes aus zwei Schlüssel, einen öffentlichen und einen geheimen.
\n
Gegeben ist eine Zahl p aus zwei Primzahlen als modulus. Die Zahlen werden jeweils mit 1 minuiert, das Produkt plus 1 ist phi(p). Dieses wiederum wird ebenfalls faktorisiert, die Faktoren sind e und d und dienen jeweils als Exponent bei der Verschlüsselung. Der Faktor e ist bekannt (öffentlicher Schlüssel) und ist der Exponent zum Kodieren nach dem Schema:
\n
zu verschlüsselnder Text => Umformung in Zahlen gemäß Alphabet oder pipapo => Basis
\n
Verschlüsselung: Basis 'hoch' Exponent e modulo geteilt durch p. z.B: 1002^97 modulo 3713. Das Ergebnis 1406 lässt sich mit einem geeigneten Programm* berechnen (*folgt in Kürze hier auf unseren ckc Seiten!).
\n
Programmauszug:
\n
283ungerade aw, ba:z, modzug, modzz, x 97 1406 1406 2
\n
Für die Entschlüsselung zurück von 1406 zu 1002, verwendet man den hier thematischen anderen Faktor von phi(p)+1 = e*d, also d.
\n
Mit 1406 hoch 37(d) modulo 3713 erhält man den verschlüsselten Text \"1002\":
\n
Programmauszug:
\n
283ungerade aw, ba:z, modzug, modzz, x 37 1002 1002 2
\n
Das Verfahren gilt insofern als sicher, weil nur p bekannt ist, nicht aber phi(p)+1, und die Faktoren von p bei großen Zahlen (mit non-verbaler Stellenzahl, also auch wesentlich größer als im Beispiel) nur mit relativ viel Aufwand erschlossen werden können. Ebenso folgen die Faktoren von phi(p) nicht einfach aus phi(p)+1, sondern müssen ebenfalls durch Faktorisierung gefunden werden - üblicherweise ist das sehr viel leichter. Bietet sich also phi(p)+1 an, da von der Zahl immerhin ein Faktor bekannt ist. Aber phi(p)+1 selbst ohne die Faktoren von p eigentlich nicht!
\n
Es gibt noch eine weitere Möglichkeit, den \"inversen\" Exponenten d für die Rückverwandlung des kopierten Textes zu finden - man kann z.B. einfach e als Basis der modulo-Rechnung nehmen - dann muss man allerdings mit Exponenten in einem geschätzten Zahlenbereich von e bzw (phi(p)+1)/e nach d suchen, wofür man ein sehr effizientes modulus-Programm braucht (Vorankündigung!). Im hiesigen Beispiel ist e aber z.B. nur 97, und d = 37.
\n
Es gibt aber glücklicherweise eine algebraische Methode, mit der man d exakt finden oder so annähern kann, dass d mit Hilfe der modulus-Strategie exakt bestimmbar ist. Mit d hat man dann den geheimen Schlüssel in der Hand, auch wenn man eigentlich nur den öffentlichen Schlüssel e und den modulus p kennen dürfte...
\n
Das hier vorgestellte Programm gibt bei Eingabe des modulus p (Teilen mit Rest durch p) und des Faktors e von phi(p)+1 den Faktor d = (phi(p)+1)/e aus:
\n
diffiehackhtml.html funktioniert erst nach weiteren Installationen
\n
diffiehack.py könnt ihr downloaden * demnächst mit *Aidaifm* unserer kleinen Maschine für moduli mit bis zu 100 digits
\n
Das algebraische Prinzip
\n
Kerngedanke ist, dass p und phi(p)+1 nahe oder gleiche (untere) Quadratbasen haben, also bezüglich der Zerlegung in approximative Wurzeln und deren Rest sowie in den resultierende Darstellungen als Quadratdifferenzen so ähnlich sein müssen, wie es sich in Abhängigkeit von der Faktorengröße von p und der Berechnungsvorschrift von phi(p)+1 ergibt.
\n
p = prim1 * prim2
\n
phi(p)+1 = (prim1 - 1)*(prim2 - 1) + 1
\n
Die Faktoren e und d für die Verschlüsselung und Entschlüsselung von nummerisierten Texten sind Faktoren von phi(n)+1, von denen e öffentlich ist, d aber geheim und nicht einfach zu berechnen (eigentlich), da phi(p)+1 nur berechnet werden kann, wenn die Faktoren prim1 und prim2 von p bekannt sind. Diese Faktoren zu finden, ist üblicherweise nicht wirklich einfach oder schnell zu machen, wenn die Zahlen entsprechend groß sind.
\n
Ein Beispiel in kleinen Zahlen für die Ähnlichkeit von p und phi(p):
\n
p = 2109 = 19 * 111 = 65^2 - 46^2
\n
phi(p) = 1980 = 18 * 110 = 64^2 - 46^2
\n
Diese Eigenschaft führt dazu, dass über die approximative Wurzel nicht nur ein Faktor von p geschätzt werden kann, sondern auch von phi(p), und sowohl p als auch e zur Korrektur der Approximation geeignet sind.
\n
Im Programm sieht diese Annäherung hin zum potenziellen Faktor von phi(p)+1, test1d, wie folgt aus:
\n
prox = int(p**0.5)
proxf1 = (prox + 1)**2
rest1 = proxf1 - p
fakt1 = prox + 1 + rest1
fakt12 = int(p / fakt1)
phip1 = (fakt12-1) * (fakt1-1)
test1d = int((phip1+1)/e)
\n
Die besten Ergebnisse erhält man, wenn e der größere Faktor von phi(p)+1 ist.
\n
Eine typische Unschärfe ist e +-2 durch die Reduktion auf die ganzzahlige Wurzelapproxmation etc.
\n
Daher kann man das Programm noch um den alternativen Fall e+2 ergänzen (siehe unten)
\n
Das Programm kann auch zur Zerlegung multifaktorieller Zahlen verwendet werden. Dabei ergibt sich phi(p) jeweils passend zu den diminuierten Faktoren von p. Die Schätzung ist Faktoren in der Regel korrekt, wenn die Zahl dadurch vollständig analysiert wird.
\n
\n
Das Programm ist unten in den Text kopiert, es kann auch online getestet werden.
\n
Die Programmausgabe des Beispiels aus dem Text:
\n
Eingabe modulus p: 3713
Eingabe Faktor e von phi(p)+1: 97
Eingabe p, e: 3713 97
bekannter Wert modulus p und e (bekannter Faktor von phi+1): 3713
bekannter Wert e (bekannter Faktor von phi+1): 97
Ergebnis: berechnetes phi+1 = e * berechneter Faktor : 3395 = 97 * 35
Ergebnis mit typischer Unschärfe: berechnetes phi+1 = e * berechneter Faktor+2 : 3589 = 97 * 37
Zusatzinfo:
Zielwerte: phi+1, e, h 3589 97 37
Abweichung phi+1, Faktor: 194 2
passende Faktoren von p: q, tq 79 47
\n
\n
\n
Weitere Beispiele:
================ RESTART: ===============
Eingabe modulus p: 174592903
Eingabe Faktor e von phi(p)+1: 65927
Eingabe p, e: 174592903 65927
bekannter Wert modulus p und e (bekannter Faktor von phi+1): 174592903
bekannter Wert e (bekannter Faktor von phi+1): 65927
Ergebnis: berechnetes phi+1 = e * berechneter Faktor : 174508769 = 65927 * 2647
Zusatzinfo:
Zielwerte: phi+1, e, h 174508769 65927 2647
Abweichung phi+1, Faktor: 0 0
passende Faktoren von p: q, tq 82007 2129
================ RESTART: ===============
Eingabe modulus p: 2291478107
Eingabe Faktor e von phi(p)+1: 198479
Eingabe p, e: 2291478107 198479
bekannter Wert modulus p und e (bekannter Faktor von phi+1): 2291478107
bekannter Wert e (bekannter Faktor von phi+1): 198479
Ergebnis: berechnetes phi+1 = e * berechneter Faktor : 2291043097 = 198479 * 11543
Zusatzinfo:
Zielwerte: phi+1, e, h 2291043097 198479 11543
Abweichung phi+1, Faktor: 0 0
passende Faktoren von p: q, tq 429679 5333
================ RESTART: ===============
\n
Eingabe modulus p: 18014624883243766243
Eingabe Faktor e von phi(p)+1: 554651656049
Eingabe p, e: 18014624883243766243 554651656049
bekannter Wert modulus p und e (bekannter Faktor von phi+1): 18014624883243766243
bekannter Wert e (bekannter Faktor von phi+1): 554651656049
Ergebnis: berechnetes phi+1 = e * berechneter Faktor : 18014623763642031183 = 554651656049 * 32479167
Ergebnis mit typischer Unschärfe: berechnetes phi+1 = e * berechneter Faktor+2 : 18014624872945343281 = 554651656049 * 32479169
\n
\n
================ RESTART: ===============
\n
\n
Eingabe modulus p: 8282149
Eingabe Faktor e von phi(p)+1: 2011
Eingabe p, e: 8282149 2011
bekannter Wert modulus p und e (bekannter Faktor von phi+1): 8282149
bekannter Wert e (bekannter Faktor von phi+1): 2011
Ergebnis: berechnetes phi+1 = e * berechneter Faktor : 8271243 = 2011 * 4113
Zusatzinfo:
Zielwerte: phi+1, e, h 8275265 2011 4115
Abweichung phi+1, Faktor: 4022 2
passende Faktoren von p: q, tq 5333 1553
\n
Die typische Abweichung um 2 haben wir in das Programm integriert.
\n
\n
******************************************************************************************************************
\n
\n
DAS PROGRAMM *DIFFIESYSTEMHACK 15145 * 262359
\n
import math
import sys
from sys import argv
import csv
from csv import reader
import re
import itertools
import pickle
import typing
from datetime import datetime
import cmath
import time
p = int(input(\"Eingabe modulus p: \"))
e = int(input(\"Eingabe Faktor e von phi(p)+1: \"))
#(c) Dr. Ulrike Ritter (ckcgt)
t=1
print(\"Eingabe p, e:\", p, e, \"\n\")
prox = int(p**0.5)
proxf1 = (prox + 1)**2
rest1 = proxf1 - p
fakt1 = prox + 1 + rest1
fakt12 = int(p / fakt1)
phip1 = (fakt12-1) * (fakt1-1)
test1d = int((phip1+1)/e)
if test1d %2 == 0:
test1d = test1d -1
test2d = test1d+2
phin1res = e*test1d
phin2res = e*test2d
print(\"bekannter Wert modulus p und e (bekannter Faktor von phi+1):\", p, \"\n \")
print(\"bekannter Wert e (bekannter Faktor von phi+1):\", e, \"\n \")
print(\"Ergebnis: berechnetes phi+1 = e * berechneter Faktor :\", phin1res, \"=\", e, \"*\", test1d, \"\n \")
print(\"Ergebnis mit typischer Unschärfe: berechnetes phi+1 = e * berechneter Faktor+2 :\", phin2res, \"=\", e, \"*\", test2d, \"\n \")
prox = int(p**0.5)
st= prox+1
t=3
for t in range(3, st):
t = st - t
fm1 = p % t
if (fm1 == 0 and p > t):
q = int( p/t)
tq = int(p/q)
phie = q-1
phih = tq-1
phin= (phie* phih)+1
hmod = phin % e
if (hmod == 0 and phin > e):
h = int(phin/e)
vali1h = h - int(test1d)
phical1h = phin - e*test1d
print(\"Zusatzinfo: \n\")
print(\"Zielwerte: phi+1, e, h\", phin, e, h, \"\n \")
print(\"Abweichung phi+1, Faktor:\", phical1h, vali1h, \"\n \")
print(\"passende Faktoren von p: q, tq\", q, tq , \"\n \")
#break
#Vom Mittelwert der Faktoren von phi1 auf die Quadratbasen, alternativ 1 und 2
#dann durch Vergleich mit p ob 1 oder 2 entscheiden
mwdiff = p - phin1res
oqbphi = int(mwdiff/2)
oqbp = int((mwdiff/2)+1)
uqbp = (oqbp**2 - p)**0.5
uqbpin= int(uqbp)
if (uqbpin == uqbp):
uqbphi = (oqbphi**2 - phin1res+1)**0.5
f1phi = oqbphi - uqbphi
f2phi = oqbphi + uqbphi
f1p = oqbp - uqbp
f2p = oqbp + uqbp
ptest = f1p * f2p
if (ptest == p):
uqbphi = (oqbphi**2 - phin1res+1)**0.5
f1phi = oqbphi - uqbphi
f2phi = oqbphi + uqbphi
phitest = f1phi*f2phi
print (\"Faktoren von p: f1p, f2p; \", p, f1p, f2p,)
print(\"Faktoren von phi: f1phi, f2phi\", phin1res-1, f1phi, f2phi)
print (\"Quadratbasen von p: oqbp, uqbp; Quadratbasen von phi: oqbphi, uqbphi\", p, oqbp, uqbp, phitest, oqbphi, uqbphi)
if not(uqbpin == uqbp):
mwdiff = p - phin2res
oqbphi = int((mwdiff/2))
oqbp = int((mwdiff/2)+1)
uqbp =( abs(oqbp**2 - p))**0.5
uqbpin= int(uqbp)
if (uqbpin == uqbp):
f1p = oqbp - uqbp
f2p = oqbp + uqbp
ptest = f1p * f2p
if (ptest == p):
uqbphi = (oqbphi**2 - phin2res+1)**0.5
f1phi = oqbphi - uqbphi
f2phi = oqbphi + uqbphi
phitest = f1phi*f2phi
print (\"Faktoren von p: f1p, f2p\", p, f1p, f2p)
print(\"Faktoren von phi: f1phi, f2phi\", phin2res-1, f1phi, f2phi)
print (\"Quadratbasen von p: oqbp, uqbp; Quadratbasen von phi: oqbphi, uqbphi\", p, oqbp, uqbp, phitest, oqbphi, uqbphi)