Got zum Gruße
habe mal ne Frage will meine Datenkommunikation verschlüsseln.
Habe da was im inte gefunden
Beispiel für eine RSA-Verschlüsselung
Gegeben:
p=61 [erste Primzahl]
q=53 [zweite Primzahl]
n=p*q=3233 Modulus [Teil des öffentlichen Schlüssels]
e=17 [öffentlicher Exponent (Teil des öffentlichen Schlüssels)]
d=2753 [geheimer Exponent (der geheime private Schlüssel)]
c=m^17 mod 3233 [Verschlüsselungsvorschrift]
d=c^2753 mod 3233 [Entschlüsselungsvorschrift]
Aufgabe 1:
Verschlüssele die Zahl m=123
Ergebnis 1:
c=123^17 mod 3233=
337587917446653715596592958817679803 mod 3233 = 855
Aufgabe 2:
Entschlüssele die Zahl c=855
Ergebnis 2:
d=855^2753 mod 3233 =
5,0432888958416068734422899127394e+8071 mod 3233 = 123
ist das auf einen 128 iger zu machen????
in DEV c++ gehts nicht kommt was anderes heraus.
int p,q,e,n,d;
double c,dec;
p=61;
q=53;
n=p*q;
e=17;
d=2753;
c=123;
int i=0;
for(i=0;i<e;i++)
{
c *=c;
}
c= (int)c % n;
printf("ERGEBNISS %e",c);
gibt es schon so was für avr ????
die avr crypt lib ist mir zu unübersichtlich da blicke ich nicht durch
Danke
Hallo,
ich vermute mal das wird nichts. Bzw welche geschwindigkeit ist denn
gefordert?
Per RSA eine datenstrom zu verschlüsseln, macht eh keinen sinn wird
nicht mal bei VPNs oder HTTPs gemacht. Per RSA wird nur der 1 Schlüssel
ausetauscht und der rest läuft über DES/3DES/AES ab.
Wenn es also nur um eine Verschlüsselte verbindung geht zwischen 2
punkten die du unter kontrolle hast dann nimmen eine Festen schlüssel
und das AES verfahren. Das ist dafür ausgelegt wenig resourcen und gut
in hard und software zum implementieren sein. Ich vermute mal das hat
auch schon jemand für AVRs getant.
mfg
>>Ergebnis 1:>>c=123^17 mod 3233=>>337587917446653715596592958817679803 mod 3233 = 855
dass das so nicht gehen wird liegt wohl an dem ergebnis von 123^17..
ich kenn keinen Datentyp der so eine Zahl fassen könnte
MfG
hindert doch keinen einen eigenen datentyp zu schaffen. zahlen deutlich
über 64bit sind gar kein problem.
die beschränkung ist nur der ram. und da sehe ich auch das problem beim
mega128.
der schlüssel muss schon groß sein um halbwegs sicher zu sein also
mindestens 150 stellige primzahlen. davon 2 und natürlich die
multiplikation zwischen beide.
beim verschlüsseln kommt dann noch das orginal mit 300 stellen dazu und
das verschlüsselte teil mit 300 stellen. (also immer mindestgrößen)
aarrrgghh :-)
Ich rede ja auch die ganze Zeit davon,
dass Mist rauskommen MUSS, wenn man nen
Standard-Double für so ne Zahl nimmt.
Klar kann man sich immer was basteln,
aber das war ja gar neicht meine Aussage.
MfG
Du musst die modulare Exponentation anders durchführen dann geht das
auch bei deinen Zahlengrößen auf einem AVR. Statt erst 123^17
auszurechnen und dann mod 3233, baust du eine binäre modulare
Exponentation bei der in jedem Zwischenschritt mod 3233 gerechnet wird.
Alle Zwischenresultate können dann 3233^2 nicht überschreiten und das
passt sauber in einen long.
Aber was bringt dir das am Ende ? Einen 12Bit-RSA und den knackt dir
jeder in Millisekunden. Wenn du mit RSA auf der sicheren Seite sein
möchtest musst du mit Schlüsselgrößen im Bereich 1024 Bit bis 4096 Bit
arbeiten, also mit Zahlenbereichen intern von bis zu 2^8192 ! Das geht
sicherlich auch auf dem AVR mit ausreichend SRAM zu berechnen dauert
dann halt Minuten für eine Berechnung.
Im WEB habe ich schonmal eine RSA-AVR Umsetzung gesehen, suche mal
danach.
Gruß Hagen
Das man andere kryptographische Protokolle machen kann die andere
Features ermöglichen. Man kann zb. per Zufall erzeugte Schlüssel
benutzen um Daten zu verschlüsseln und sie dann zu übertragen. Man muß
sich also nicht auf einen festen Schlüssel vorher einigen sondern
benötigt nur einen öffentlichen RSA Schlüssels des Empfängers. Mit
diesem kann man Daten nur verschlüsseln aber nicht mehr entschlüsseln.
Gruß Hagen
in diesem fall geht es aber um die schlüsselung eine datenstromes,
vermutlich zwischen 2 bekannten partner. Also was ist einfacher sich
auf eine 128byte AES key festzulegen und ihn per Telefon oder Brief oä.
beiden partner bekannt zu machen und dann damit einfach die daten
übertragen. Der RSA schlüsselaustausch mit 1024bit stellt selbt für
richige PC noch ein grosse rechenaufgabe, das in einem µC zu machen
macht wenig sehr wenig sinn.
Bei RSA ist fast der ganze speicher dem private key und dem public key
der gegenstelle voll oder wie will man sonst min-in-middle attack
ausschliessen.
Naja das zerpflücke ich mal:
1.) entscheidend ist die Zielsetzung diese definiert den notwendigen
Funktionsumfang. Wenn es also heist hole Daten sicher von einem SSL
Server per TCP/IP ab dann benötogt man RSA
2.) welcher Speicher ist voll ? Ein vollständiger RSA und ein
öffentlicher RSA benötigt nicht mehr als 2k FLASH. Das passt in einem
ATMega256 ja wohl lässig rein.
3.) man benötigt bei einer Oneway Verbindung zu einem Server nur dessen
öffentlichen RSA Schlüssel und nicht den Privaten. Der Öffentliche
Schlüssel kann nur aus einer 1024 Bit Zahle bestehen und einer harcoded
16 Bit Zahl als public Exponent, zb. 0x10001.
Soll der Client auch Daten empfangen können die explizit an ihn
addressiert wurden dann benötigt man noch einen vollständigen RSA
Schlüssel für diesen Client. Dieser bestünde aus P,Q = 512 Bit, D=1024
Bit private Decryption Exponent, E=16Bit als public Exponent, meist
harcoded, und eventuell noch N=1024Bit als vorausbeechnetes public
Modul, also N=P*Q.
4.) bei 1024Bit RSA und cleverer Programmierung benögtigt man als
temporäre Daten im SRAM minimal 1024Bit*3 = 384 Bytes. Einmal als 2048
Bit Zwischenspeicher bei der Exponentation und 1024 Bit um für die
modulare Reduktion das Modul zu speichern. Selbst dieses könnte man fix
im FLASH speichern und somit benötigt man nur 256 Bytes an SRAM.
Die Speichermenge ist also garnicht das Problem.
Es ist das Fehlen einer HW-Division das eher die probleme bei der
Umsetzung bereitet. Der Verbrauch an FLASH für den Code um per Software
eine solche Division=modulare Reduktion zu bauen übersteigt auf einem
AVR den Verbrauch für die Schlüssel bei weitem. Mal abgesehen das diese
Division auch der Performancetechnisch Flaschenhals darstellt.
Gruß Hagen
1.) entscheidend ist die Zielsetzung diese definiert den notwendigen
Funktionsumfang. Wenn es also heist hole Daten sicher von einem SSL
Server per TCP/IP ab dann benötogt man RSA
Das ist richtig, aber davon steht nichts in der ersten Beschreibung.
Aber das ist mal ein sportliche aufgabe für ein µC
2.) welcher Speicher ist voll ? Ein vollständiger RSA und ein
öffentlicher RSA benötigt nicht mehr als 2k FLASH. Das passt in einem
ATMega256 ja wohl lässig rein.
OK, da ich bist jetzt immer kleinere sachen gemacht habe, hatten
meine AVRs noch nicht mehr als 2Kb.
3.) man benötigt bei einer Oneway Verbindung zu einem Server nur dessen
öffentlichen RSA Schlüssel und nicht den Privaten. Der Öffentliche
Schlüssel kann nur aus einer 1024 Bit Zahle bestehen und einer harcoded
16 Bit Zahl als public Exponent, zb. 0x10001.
Der Private Schlüssen der gegenstelle sollte NIE auftauchen, aber
einen eigenen Private key sollte der AVR schon haben.
Die eigentliche Division sollte vom Code her nicht so viel sein, das
Problem ist eher die Geschwindigkeit.
Naja die Division ist schon Codeintensiv. Man Dividiert ja nicht zwei
8Bit Zahlen sondern eine 256Bytes Zahl mit einer 128Bytes Zahl. Die
Multiplikation/Addition/Subtraktionen sind trivial und relativ effizient
zu machen, da sie vom LSB zum MSB arbeiten. Die Divison arbeitet aber
immer vom MSB zum LSB und ist komplex. Man könnte und sollte auch diese
Division, bzw. modulare Reduktion durch den Montgomery Trick ersetzen.
Dieser arbeitet nur mit Multiplikationen. Alternativ bietet sich für den
AVR auch die Barret Reduktion an. Ansonsten bleibt nur noch die Division
nach D.Knuth. Diese stetzt sich zusammen aus Shifts, Multiplikationen,
Subtraktionen und Additionen, und einer Eingangs Approximation per
Division über 3 Digits = 24Bit minimal. Alle Operationen natürlich über
128 Bytes große Zahlen. Das summiert sich. In meiner Large Integer
Bibliothek für den PC umfassen die verschiedenen
Multiplikationensalgorithmen ca. 70% der kompletten Bibliothek. Über
diese werden auch die Divisionen gemacht. Diese Bibliothek ist ca. 10
mal größer im Code als die eigentliche RSA Implementierung am Ende.
Auf MCUs würde ich sowieso nur mit Elliptischen Kuren in GF(m^2^n)
arbeiten. Da dort eine Addition/Subtraktion per XOR erfolgt, es
effiziente Multiplikationen gibt und kein algorithmischer Unterschied
zwischen Division und Multiplikation existiert. Davon abgesehen
reduziert sich die Zahlengröße um Faktor 3.5 bei gleicher Sicherheit im
Vergleich zu RSA und dem Arbeiten in N(p). Das bringt
Performancetechnisch eine Verbesserung um mindestens Faktor 10. Dumm
daran ist nur das wenn man heutigen Standardsystemen gerecht werden
möchte, also zb. SSL, die ECC GF(m^n) garnicht unterstützt werden.
Generell ist es die beste Taktik wenn man asymmetrische Kryptographie
umgehen kann. Also wie schon mal gesagt auf RSA und Konsorten verzichten
kann und mit simplen symmetrischen Verfahren arbeitet. Denn wenn man RSA
benötigt dann muß man denoch alle nötigen symmetrischen Verfahren
integrieren, also zb. AES und SHA1. Mit allen asymmetrischen Verfahren
die auch Daten für eine Kommunikation verschlüsseln möchte arbeitet man
in hybrider Bauweise mit symmetrischen Verfahren zusammen. Das hat
primär nichts mit der Effizienz zu tun sondern mit kryptographsichen
Anforderungen. Einen Datenstrom mit RSA zu verschlüsseln ist nämlich
kryptographisch unsicher.
Gruß Hagen
Ist es möglich das hier zu implementieren???
http://de.wikipedia.org/wiki/Digital_Signature_Algorithm
Stelle mir folgendes vor
Ich habe messwerte im FLash ATMEL FLASH.
Wen ich diese aus dem Flash über nen AVR ziehen will muß er den Stream
signieren alles zusammen wregibt dann eine Prüfsumme.
z.b 1000 Messwerte haben dann eine Prüfsumme x diese wird mit
übermittelt.
wenn nun in den daten manipuliert wird stimmt die Prüfsumme nicht
überein und das Auswerte Programm merkt dies und gibt eine Warnung aus.
möglich ist alles nur ob es Sinn macht ist die Frage.
In deinem Falle würde ich ein besseres "Prüfsummenverfahren" benutzen,
also kryptographisch sicheres. Das könnte zb. MD4 sein, aber auch dieses
wäre noch oversized.
Ich würde eine 32Bit CRC nehmen. Über deine Daten berechnest du damit
eine Prüfsumme. Dann erzeugst du noch 32Bit Zufall. Die 4 Bytes Zufall
xor'verknüpfst du mit den 4 Bytes CRC32. Die 4 Bytes Zufall und 4 Bytes
xor'verknüpfte CRC32 werden nun ihrerseits mit 8 Bytes Passwort
xor'verknüpft. Das Passwort ist geheim, per Zufall einmalig gewählt und
hardcoded im AVR und auf Empfängerseite gespeichert. Das 8 Bytes
Resultat sendest du mit den Daten.
Das ist zwar kryptographisch betrachtet nicht sicher aber efffizient auf
einem AVR, einfach, und schonmal eine zu nehmende Hürde.
Noch besser ist es mit einer guten Verschlüsselung die kompletten Daten
zu verschlüsseln. Die Daten bestehen dann aus 8-16 Bytes Zufall am
Anfang, dann deine Messwerte und dann nochmal eine 8 Bytes Signatur,
fest vorgegeben oder Teile des Passwortes. Als Verschlüsselung ein
symmetrisches Verfahren wie AES/DES/XTEA/RC5 das mit dem entsprechenden
Feedbackmodus arbeitet, zb. Doppel-CBC. Dieser Feedbackmodus stellt
sicher das sich alle Datenbits die verschlüsselt werden durch alle
nachfolgenden Datenbits propagieren. Das bedeutet: nur wenn mit dem
richtigen Passwort entschlüssellt wird und nur wenn alle Datenbits
unverändert/unmanipuliert empfangen wurden kann am Ende der
Entschlüselung die 8 Bytes Signatur am Ende korrekt entschlüsselt
werden. Somit dient diese Verschlüsselung nicht nur zum Schutz vor dem
Mitlesen der Daten sondern auch als "Prüfsumme" gegen
Fehlübertragungen/Manipulationen der Daten. Das Passwort ist 16 bytes
lang, zufälig gewählt und hardcoded im AVR und Empfänger gespeichert.
Sowas lässt sich auf einem AVR relativ leicht implementieren, wesentlich
leichter als DSA oder andere asymmetrische Signaturverfahren.
Exakt dieses Verfahren habe ich in meinem AVRootloader verwendet, ein
Bootloader. Ich benutze dabei XTEA und Doppel-CBC und eine 4 Bytes
Signatur. Der Overhead ist 700 Taktzyklen pro Datenbyte. Nutzt du AES in
Software ist es nochmals langsammer, du findest bei Atmel ein AppNote
die AES implementiert.
Gruß Hagen
Ich hatte es mir so gedacht wie es auch in der Fliegerrei mit den IGC
Files gemacht wird das scheint ziemlich ischer zu sein.
Dort wird alles wichtige in dem Fall die B-Records mit einen private key
eine digitale Signatur erzeugt und diese als G-Record angehangen.
wenn jetzt einer dort was ändert stimmt die signatur nicht mehr.
Validiert werden die Brecords mit dem öffentlichen schöüssel.
Ich kenne Firmen die haben das auf einen Mega 128L geschafft FLARM.
im internet finde ich aber nur source von hash ohne schlüssel.
Für mich ist das absolutes neuland.
Danke
Rainer L wrote:
> Ich habe messwerte im FLash ATMEL FLASH.>> Wen ich diese aus dem Flash über nen AVR ziehen will muß er den Stream> signieren alles zusammen wregibt dann eine Prüfsumme.
Darf der PC den Signaturschlüssel kennen? Wenn nein, dann brauchst du
RSA/DSA. Wenn ja, dann reicht eine einfache Hash-basierte Signatur (MD5
oder SHA1 etc.), die schafft auch ein AVR locker.
http://de.wikipedia.org/wiki/HMAC
DER AVR kennt den Privaten Schlüssel und eine DLL den Öffentlichen
Schlüssel.
SHA1 habe ich implementiert geht gut und schnell.
Nur wie kann ich einen Privaten und Öffentlichen Schlüssel einbinden???
Hier die SHA1 habe ich aus einer crypt lib.
Danke
Also nach diesen Verfahren muß es laufen und noch auf den AVR umgesetzt
werden.
http://de.wikipedia.org/wiki/Digital_Signature_Algorithm
Den hash einer Datei habe ich schon portiert nun muß cih noch einen
Öffentlichen und Privaten Schlüssel erzeugen und meinen Hashwert
signieren.
Die Signatur wird von der dll gelesen und ebenso der Hashwert der Datei.
Die Signatur wird mit hilfe des Keys entschlüsselt und bekoomt dann den
Hashwert der vom AVR erzeugt wurde und übermittelt wurde.
nun soll verglichen werden errechnete hash der dll und encrypted hash
wenn gleich ist file nicht verfälscht wenn nicht ist verfälscht.
Danke
Nun muß es noch in den AVR rein.
Danke
Hoffe du gehst nicht so blauäugig an die Sache ran. Ich habe 5 Jahre
meiner Hobbyzeit mit dem Kram verbracht bis ich alles soweit umgesetzt
und auch verstanden hatte. Gerade die Elliptischen Kurven sind aus
mathematischer, kryptographsicher und aus programmiertechnischer Sicht
sehr anspruchsvoll. Einfach eine fertige Library nehmen ist die eine
Seite, es auch verstanden zu haben die Andere. Bei den ECCs solltest du
versuchen an den IEEE P1363 Standard ranzukommen, den gabs mal im WEB
auch kostenlos und frei zugänglich.
Meine ECC Implementierung in GF(p) umfasst ca. 2500 Sourcezeilen, für
den PC geschrieben und das ohne die notwendige Large Integer Library,
gerechnet. Ok, das enthält dann aber auch die Erzeugung solcher Kurven
die meistens, wenn man vorgefertigte Kurven ohne Überprüfung vertrauen
möchte, auch weglassen wird. Wie gesagt, ich denke das ist kein Projekt
für mal eben zwischendurch.
Das was du bei Wikipedia unter RSA/DSA und ECDSA findest ist nur die
grobe Mathematik.
Gruß Hagen
