RSA titkosítás AVR-rel

norbi

Hello mindenkinek!

Lenne egy feladat, amiben AVR-rel kellene megoldani az RSA titkosítást, utánna is néztem már, hogy miből is áll ez, de kiváncsi lennék, hogy valaki foglalkozott-e már ezzel AVR szinten?

Alapból már ott kezdődik a "gond", hogy kell 2db 10számjegyű prímszámot találni mindig, majd ezeket össze kell szorozni, de íme inkább képlettel, leírással:

Generálni kell két nagy prímet:

p1 és p2 (titkos)

Fontos, hogy a prímek tényleg nagy számok legyenek, általában kb. 100 decimális számjegyből állnak. Annak eldöntése, hogy a generált számok valóban prímek-e, pontosan ugyanolyan nehéz feladat, mint az RSA titkosítás brute force-szal való feltörése, mert több, mint száz jegyű szám faktorizálása nagyon sokáig tart.

Ezután elő kell állítani az

n = p1 . p2 (nyilvános)

illetve az

m = (p1 - 1) . (p2 - 1)

számokat.

Generálni kell egy véletlen

e (nyilvános)

számot úgy, hogy m és e relatív prímek legyenek.

Véletlen szám előállítására azt gondoltam ki, hogy egy AD-bemenetre a tápot kötöm s az itt vett zajból gfenerálnám.

Annak eldöntése, hogy az m és az imént generált e szám relatív prímek-e, egyszerű feladat: a legnagyobb közös osztó az euklideszi algoritmus segítségével O(log(n)) lépésben meghatározható, s ha az 1, akkor relatív prímek.

Meg kell határozni az e szám multiplikatív inverzét modulo m:

d = e-1 (mod m) (titkos)

azaz

e . d = 1 (mod m)

Az e szám inverzét, azaz a d számot az inverz euklideszi algoritmus segítségével határozzuk meg.

Az információ, egy x szám (x < n) titkosítása ezután a következőképpen történik:

y := xe (mod n)

azaz a nagy számok hatványozása algoritmus segítségével.

Nagyjábol ennyi lenne az RSA

Menni fog ez AVR-rel?

kisstam05

Szerintem ez így nem menne, mivel ha nem tévedek nagyot akkor az integer típus amit képes tárolni az 65535. Ennél nagyobbakat már ( vagy longintben de az is korlátos) tömbben tárolt számjegyekkel oldják meg.
Arra meg hogy működik-e a moduló aritmetika , hááát , nem nagyon hiszem. De a többi az menne

csak a lényeg nem.

128-as DES nem elég?
Atmel oldalon van hozzá minta is....

RSA-t nem találtam:(

norbi

Az a baj, hogy ha fizető eszközzel kapcsolatos dologról van szó, RSA kell. Úgy látom (google), hogy senki sem vágott neki ennek AVR-rel, kérdés, hogy senkinek nem volt dolga ezzel, vagy pedig nem igazán működne jól....

Az atmelen a tripla DES ott van...
A feltorese >10 ev

Vagy alternativkent a kulso EEPROM alapú Cryptoeeprom a járható út. Ezzel az RSA jarhato ut lesz...

norbi

Csak az a baj ezekkel, hogy nem védenek az ethernet csomagoknál

Mert a rendszert soroson kommunikál a fizetőeszközzel, megkapja a kártyaadatokat, s ezt továbítja TCP/IP protokollon a szervernek s ide kell az RSA.

nobody_hun

Könyvben publikáltak róla:
springerlink.com/content/87aejjlhqn6fuxpy

Azt mondja:
"On an Atmel ATmega128 at 8 MHz we measured 0.81s for 160-bit ECC point multiplication and 0.43s for a RSA-1024 operation with exponent e=216+1"

Nem túl lassú a 0,43sec?

norbi

Nem lenne sok...csak a lényeg most, hogy működjön.

Elkezdtem írni a programot, előre kiszámolt értékeket használok, hogy most csak egy részét keljen leprogramozni (a többit majd akkor, ha ez megy).

De elekadtam a hatványozásnál...

ez mért nem jó:

Kód: Egész kijelölése

Dim Y_1 As Double 
Dim Y as Double
Dim X As Double
Dim E As Double 
 
X=17
E=101

Y_1 = X ^ E
Y = Y_1 Mod N

Tudom, hogy itt X és E nem kellene doble legyen, de a későbbiekben az lesz.
Ez jön ki Y_1-nek: 272.000000000466E-3 (sorosportra küldöm ki)

Miért?

kapu48

Double=
Double. Doubles are stored as signed 64 bit binary numbers. Ranging in value from 5.0 x 10^–324 to 1.7 x 10^308

17^101=1.88512893373e+124

norbi

Akkor ez, hogy működne jól Bascom-ul?

Mert így az utolsó sornak:

Kód: Egész kijelölése


Y = Y_1 Mod N               'Jelenleg az N is double

...0 lesz az eredménye. S ha meg nem double-ben van az Y_1, akkor is 0, vagyis rossz....

Sebaj, újra nekifutok, de most csak integerekkel!

A belső kerekítések miatt, illetve hogy a tizedesek a 2 negatív hatványaival vannak számolva....

norbi

Eddig ennyire jutottam (közben egy kissebb hardver hiba is volt...):

Kód: Egész kijelölése

'Kulcsgenerálás:
Dim P As Single                                             'Egyik prím
Dim Q As Single                                             'Másik prím
Dim N As Single                                             'Prímek szorzata

Dim E As Single                                             'Váletlen szám

Dim D As Single                                             'A titkos kulcs kitevője
Dim D_1 As Single

Dim Fi_n As Single
Dim Fi_n_1 As Single                                        'Segédváltozó
Dim Fi_n_2 As Single                                        'segédváltozó


P = 13                                                      '1.prím / titkos
Q = 17                                                      '2.prím /titkos

E = 101                                                     'Véletlen szám / nyilvános

N = P * Q                                                   'N-is nyilvános
Print N

Fi_n_1 = P - 1
Fi_n_2 = Q - 1
Fi_n = Fi_n_1 * Fi_n_2                                      'Megvan a fi_n
Print Fi_n


D_1 = E ^ -1
Print D_1

D = D_1 Mod Fi_n

'Eddig ennek keéne lenni: D=e^(-1)(mod f(n))
Print D

a D papírom 172 (elvileg jó), de itt valamiért 0... Most ez magas a Bascomnak vagy pedig nekem?

norbi

Folyt.:

A MOD operátor csak single-ben működik???

Elvileg nem.....

norbi

Pedig:

x=34271896307633 'Double
y=11023 'Double

z=x mod y

Itt z=0 lesz, pedig z is double....