RSA titkosítás AVR-rel
RSA titkosítás AVR-rel
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?
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?
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.
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.
- nobody_hun
- Bitfaragó
- Hozzászólások: 425
- Csatlakozott: 2005. november 14. hétfő, 7:00
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?
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?
"Az IC-k füsttel működnek. Ha kijön belőlük a füst, nem működnek tovább." - ismeretlen szerző
"Az ID:FFFFFF egyenlő az Atmel még nem kiadott processzorával."
"Az ID:FFFFFF egyenlő az Atmel még nem kiadott processzorával."
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ó:
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?
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
Ez jön ki Y_1-nek: 272.000000000466E-3 (sorosportra küldöm ki)
Miért?
A hozzászólást 1 alkalommal szerkesztették, utoljára norbi 2009. április 23. csütörtök, 12:41-kor.
Akkor ez, hogy működne jól Bascom-ul?
Mert így az utolsó sornak:
...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!
Mert így az utolsó sornak:
Kód: Egész kijelölése
Y = Y_1 Mod N 'Jelenleg az N is double
Sebaj, újra nekifutok, de most csak integerekkel!
Eddig ennyire jutottam (közben egy kissebb hardver hiba is volt...):
a D papírom 172 (elvileg jó), de itt valamiért 0... Most ez magas a Bascomnak vagy pedig nekem?
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