www.mikrocontroller.net

Forum: Compiler & IDEs Verschlüsselungsalgo und AVR schaft er das?


Autor: Reiner L (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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

Autor: Peter (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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

Autor: Bernhard (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
>>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

Autor: Bernhard (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
>>ich kenn keinen Datentyp der so eine Zahl fassen könnte

ausser nem String :-)

Autor: Michael (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
@Bernhard: BCD

Autor: Bernhard (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
@Michael:
Das stimmt, aber ich meinte ja speziell C/C++ - Datentypen ;-)

Ansonsten haste recht

Autor: Andreas W. (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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)

Autor: Bernhard (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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

Autor: Hagen Re (hagen)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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

Autor: Peter (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
was habt ihr nur alle mit RSA? was bring RSA für den sweck für ein 
Vorteil gegenüber AES?

Autor: Hagen Re (hagen)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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

Autor: Peter (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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.

Autor: Hagen Re (hagen)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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

Autor: Peter (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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.

Autor: Hagen Re (hagen)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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

Autor: Rainer L (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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.

Autor: Hagen Re (hagen)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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

Autor: Rainer L (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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

Autor: Andreas Schwarz (andreas) (Admin) Benutzerseite Flattr this
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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

Autor: Rainer L (Gast)
Datum:
Angehängte Dateien:

Bewertung
0 lesenswert
nicht lesenswert
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

Autor: Andreas Schwarz (andreas) (Admin) Benutzerseite Flattr this
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Gar nicht, für ein asymmetrisches Verfahren brauchst du RSA, DSA o.ä. 
Deshalb meine Frage.

TinyECC sieht interessant aus: 
http://discovery.csc.ncsu.edu/software/TinyECC/

Autor: Rainer L (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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

Autor: Andreas Schwarz (andreas) (Admin) Benutzerseite Flattr this
Datum:

Bewertung
0 lesenswert
nicht lesenswert
ECDSA ist sinnvoller, muss es wirklich DSA sein? Wenn ja, stell dich auf 
minutenlange Rechnereien an.

Autor: Rainer L (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Ja natürlich DSA geht auch.
ECDSA ok.

Mal suchen ob es beispiele gibt.

Danke

Autor: Hagen Re (hagen)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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

Autor: Andreas Schwarz (andreas) (Admin) Benutzerseite Flattr this
Datum:

Bewertung
0 lesenswert
nicht lesenswert

Antwort schreiben

Die Angabe einer E-Mail-Adresse ist freiwillig. Wenn Sie automatisch per E-Mail über Antworten auf Ihren Beitrag informiert werden möchten, melden Sie sich bitte an.

Wichtige Regeln - erst lesen, dann posten!

  • Groß- und Kleinschreibung verwenden
  • Längeren Sourcecode nicht im Text einfügen, sondern als Dateianhang

Formatierung (mehr Informationen...)

  • [c]C-Code[/c]
  • [avrasm]AVR-Assembler-Code[/avrasm]
  • [code]Code in anderen Sprachen, ASCII-Zeichnungen[/code]
  • [math]Formel in LaTeX-Syntax[/math]
  • [[Titel]] - Link zu Artikel
  • Verweis auf anderen Beitrag einfügen: Rechtsklick auf Beitragstitel,
    "Adresse kopieren", und in den Text einfügen




Bild automatisch verkleinern, falls nötig
Bitte das JPG-Format nur für Fotos und Scans verwenden!
Zeichnungen und Screenshots im PNG- oder
GIF-Format hochladen. Siehe Bildformate.
Hinweis: der ursprüngliche Beitrag ist mehr als 6 Monate alt.
Bitte hier nur auf die ursprüngliche Frage antworten,
für neue Fragen einen neuen Beitrag erstellen.

Mit dem Abschicken bestätigst du, die Nutzungsbedingungen anzuerkennen.