RSA, co delam spatne

Pokračování přednášky TIN060 Algoritmy a datové struktury I
Uživatelský avatar
Donarus
Matfyz(ák|ačka) level III
Příspěvky: 194
Registrován: 30. 9. 2007 12:40
Typ studia: Informatika Mgr.

RSA, co delam spatne

Příspěvek od Donarus »

ahoj.... tak se snazim si hrat s RSAckem a nejak neco nechapu

dejme tomu mam slovo "ABC" a mam ohocnoceni takovato napriklad

A = 11
B = 93
C = 30
rozdelim do bloku po trech [119][330]

dale si zvolim dve prvocisla
p = 37 a q = 43
spocitam N = 1591
spocitam f(N) = 1512 = 2*2*2*3*3*3*7 ----> zvolim si s = 17 (mohu libovolne)

takze ted mam sifrovaci a desifrovaci funkci (x = original blok, y = zasifrovany blok)
sifrovaci : y_n = x_n^17 mod 1591


pro desifrovaci jeste musim dopocitat t (tak, aby platilo t*s = 1 (mod 1512)) ... to zvladnu pomoci eulera rozepisovat to nebudu, vyjde to 89 (zkouska: 89*17 = 1 (mod 1512))

takze mam i desifrovaci : x_n = y_n^89 mod 1591


jdu zasifrovat text:
y1: 119^17 mod 1591 = 1281
y2: 330^17 mod 1591 = 1381


tak a ted babo rad ... misto triprvkovych bloku mam najednou 4prvkove .... pritom nevim, kterou podminku porusuji, ze mi to nevychazi... :/


nevi nekdo ? -> za kazdou radu jsem vdecny....
Uživatelský avatar
Donarus
Matfyz(ák|ačka) level III
Příspěvky: 194
Registrován: 30. 9. 2007 12:40
Typ studia: Informatika Mgr.

Re: RSA, co delam spatne

Příspěvek od Donarus »

EDIT: hele napadla me jedna vec .... kdyz mi vyjde cislo vetsi jak litr, tak od nej odectu 1591 a prehodim mu znamenko na plus .. tak dostanu trociferak s kladnym znamenkem ... pak pri pouziti desifrovaci funkce desifruju, ale vyjde mi znovu cislo nad litr .. takze znovu odectu 1591 a zas prehodim hznamenko a mam v modulu trojciferak ... a funguje to, jenze pouze na par prikladech(neumim si spocitat to nekonecne velke spousto prikladu abych si to potvrdil ... tam kde jsem to zkousel je to OK), neumim si ale dokazat, ze tohle funguje obecne a nejsem si jist, jestli je to spravna varianta a neni chyba jinde..


EDIT2: je to blbost :)berme v uvahu nejake cislo (soucin p*q) ... nekde mezi 2500 a 3000 ... pak pokud dostanu napriklad vymodusenim nejake cislo 1300, a chci z nej trojciferak, tak pak odectu 2500 a dostanu se do -1200, zmenim znamenko a porad mam 4ciferak ... sakra nevim co s tim :/
Uživatelský avatar
Donarus
Matfyz(ák|ačka) level III
Příspěvky: 194
Registrován: 30. 9. 2007 12:40
Typ studia: Informatika Mgr.

Re: RSA, co delam spatne

Příspěvek od Donarus »

no tak chybu jsem nevyřešil.... zatím mám sestavenej jenom takovej textík... je to převážně opis a sjednocení z více zdrojů, ale pořád, když to se všemi těmito zdroji srovnávám, nemůžu si tu chybu najít, nebo ten algoritmus někde necápu .. Každopádně i v mých zdrojích jsem na stejné chyby narazil v tamějších příkladech tak už nevím no :D
Přílohy
RSA.pdf
(122.81 KiB) Staženo 205 x
Uživatelský avatar
hippies
Admin(ka) level I
Příspěvky: 990
Registrován: 29. 9. 2004 12:46
Typ studia: Informatika Mgr.
Bydliště: Mladá Boleslav
Kontaktovat uživatele:

Re: RSA, co delam spatne

Příspěvek od hippies »

A proč to dáváš do bloku po 3, když máš 4 ciferný n?
Chjo, dovede te si představit svět, kde by byla každá harmonická diferenciální forma (jistého typu) nesingulární projektivní algebraické variety racionální kombinací kohomologických tříd algebraických cyklů..
Uživatelský avatar
Donarus
Matfyz(ák|ačka) level III
Příspěvky: 194
Registrován: 30. 9. 2007 12:40
Typ studia: Informatika Mgr.

Re: RSA, co delam spatne

Příspěvek od Donarus »

kdyz dam do bloku po 4ech, tak nezarucim, ze ten blok mit vzdy mensi hodnotu, nez N ... nebo ta podminka nemluvi o velikosti cisla uvnitr bloku, ale o poctu cifer ??? v tomhle jsem trochu zmatenej vsude je neco jineho..

treba na blbem priklade, kdyb bysme v bloku schytali 2 ruzne hodnoty, ale pak meli tejna modula... to je vpohode jednim smerem, ale opacnym smerem uz z toho prece nemuzeme dostat original ..
:/
Uživatelský avatar
hippies
Admin(ka) level I
Příspěvky: 990
Registrován: 29. 9. 2004 12:46
Typ studia: Informatika Mgr.
Bydliště: Mladá Boleslav
Kontaktovat uživatele:

Re: RSA, co delam spatne

Příspěvek od hippies »

Ok, tentokrat sem se nad tim zamyslel:) .. No urcite by reseni bylo rozebrat do trojic posilat ctverice a na dekodovani zase brat ctverice a psat trojice;) To se ti vejde vzdycky. Ale nevim, jeslti je to tak zamysleny, mam takovej dojem, ze by zpravy mely byt po zakodovani stejne dlouhe.
Chjo, dovede te si představit svět, kde by byla každá harmonická diferenciální forma (jistého typu) nesingulární projektivní algebraické variety racionální kombinací kohomologických tříd algebraických cyklů..
Uživatelský avatar
Donarus
Matfyz(ák|ačka) level III
Příspěvky: 194
Registrován: 30. 9. 2007 12:40
Typ studia: Informatika Mgr.

Re: RSA, co delam spatne

Příspěvek od Donarus »

hippies: neboj, tohle me taky napadlo :D ale to by pak nebylo spravne.. zpravy maji byt opravdu stejne dlouhe...
Uživatelský avatar
Donarus
Matfyz(ák|ačka) level III
Příspěvky: 194
Registrován: 30. 9. 2007 12:40
Typ studia: Informatika Mgr.

Re: RSA, co delam spatne

Příspěvek od Donarus »

jako principielne ten algoritmus dokonale chapu, ale nechapu, jak se zbavit tohohle.... ja si myslim, ze to bude nejaka blbost, jako <= a < ... skoro zadny rozdil pro velka cisla, ale cim mensi, tak tim vetsi pravdepodobnost chyby :D :D no sakra... v tom PDFku jsem nacpal priklad, kterej tohle neresi, ale kdybych tam pridal libovolnej blbej znak, tak uz mi to asi fungovat nebude.. teda bude, ale udela to 4ciferak, a ja nevim co s nim :d
Uživatelský avatar
Ellrohir
Matfyz(ák|ačka) level III
Příspěvky: 140
Registrován: 21. 12. 2007 13:29
Typ studia: Informatika Bc.
Bydliště: Praha
Kontaktovat uživatele:

Re: RSA, co delam spatne

Příspěvek od Ellrohir »

lol...když tak na to teď koukám, tak můj příklad, co dělám na zápočet u Hrice a kde Hric sám definoval většinu hodnot - p=11, q=13, s=7 - a bloky mám velikosti 2 , tak mi taky vycházej některý bloky zakódovaný tříciferný...

nakonec vono je to logický, protože při operaci MOD může zjevně vyjít číslo z rozsahu 0(1) až p*q-1, takže pokud je p*q n-ciferný, tak tak se můžeš na n cifer dostat, i když blok si volíš n-1 cifernej, aby hodnota v bloku nebyla vyšší...otázka je, jak se to řeší, to sem zatím nikde neviděl :?
Uživatelský avatar
Donarus
Matfyz(ák|ačka) level III
Příspěvky: 194
Registrován: 30. 9. 2007 12:40
Typ studia: Informatika Mgr.

Re: RSA, co delam spatne

Příspěvek od Donarus »

no prave ... o to jde ... jak tohle resit.. napadla me moznost zvolit prvocisla tak, aby jejich soucin bylo cislo , ktere obsahuje vysoke cifry.... pokud bychom meli ohodnoceni abecedy takove, ze by obsahovalou pouze nizsi cifry, nez je vysledne N, pak by to bylo vpohode bo pak muzu klidne udelat stejneciferna cisla.... Ale co si budem nalhavat.. u malych N se to dosahnout da.. ale ukazte mi rozumne, ze u soucinu dvou petsetimistnych prvocisel je toto vubec mozne..... lepe receno... ono to mozne neni... takze to je taky uvaha spatnym smerem..
Uživatelský avatar
Ellrohir
Matfyz(ák|ačka) level III
Příspěvky: 140
Registrován: 21. 12. 2007 13:29
Typ studia: Informatika Bc.
Bydliště: Praha
Kontaktovat uživatele:

Re: RSA, co delam spatne

Příspěvek od Ellrohir »

no možná jenom stačí příjemci nějak "říct", že mu sypeš tak a tak dlouhé bloky (a nejlíp bloky s n ciframi (počet cifer číslo p*q), protože tuhle část klíče u sebe má)...protože to, že se to tím dešifrováním "zmenší" ti v zásadě nevadí, pokud budeš dešifrovaný části slepovat tak, jak ti budou vylejzat...což asi budeš, protože co by si s nima dělal

příklad :

veřejný klíč {7,143}
soukromý klíč {103,143}

šifruju : "CIPHERTEXT"

převedu to do ascii 99-105-112-104-101-114-116-101-120-116 a rozsekám na bloky po 2 - 99|10|51|12|10|41|01|11|41|16|10|11|20|11|6

šifrování (jenom první 3 písmena)

99^7 mod 143 = 44
10^7 mod 143 = 10
51^7 mod 143 = 116
...

pošlu jako

|044|010|116|...etc...

dešifruju jako

044^103 mod 143 = 99
010^103 mod 143 = 10
116^103 mod 143 = 51
...

výsledek

991051...

jsem tam, kde jsem byl, nic se "nezkazilo"...

spíš je ale otázka, jak si to teď příjemce interpretuje? vyleze mu nějaká posloupnost ascii kódu, ale jak zjistí, kde má udělat mezery? (že to není znak "10", ale znak "105" atd.) :shock:
svick
Matfyz(ák|ačka) level I
Příspěvky: 18
Registrován: 22. 2. 2008 19:19
Typ studia: Informatika Mgr.
Bydliště: 17. listopad

Re: RSA, co delam spatne

Příspěvek od svick »

Ellrohir píše:spíš je ale otázka, jak si to teď příjemce interpretuje? vyleze mu nějaká posloupnost ascii kódu, ale jak zjistí, kde má udělat mezery? (že to není znak "10", ale znak "105" atd.) :shock:
Já si myslím, že musíš kódovat vždy pevný počet číslic na znak, takže ne 99-105-…, ale 099-105-… A pak příjemce tu posloupnost, co dešifruje rozseká po trojicích.
Uživatelský avatar
Ellrohir
Matfyz(ák|ačka) level III
Příspěvky: 140
Registrován: 21. 12. 2007 13:29
Typ studia: Informatika Bc.
Bydliště: Praha
Kontaktovat uživatele:

Re: RSA, co delam spatne

Příspěvek od Ellrohir »

jo, to zní jako celkem rozumnej postup :)
Uživatelský avatar
Donarus
Matfyz(ák|ačka) level III
Příspěvky: 194
Registrován: 30. 9. 2007 12:40
Typ studia: Informatika Mgr.

Re: RSA, co delam spatne

Příspěvek od Donarus »

převedu to do ascii 99-105-112-104-101-114-116-101-120-116 a rozsekám na bloky po 2 - 99|10|51|12|10|41|01|11|41|16|10|11|20|11|6
dve chyby .. musis jak jiz bylo receno 099 a dale nemuze byt v bloku jedna cifra, cili samotna sestka tam nemuze byt..
Uživatelský avatar
Donarus
Matfyz(ák|ačka) level III
Příspěvky: 194
Registrován: 30. 9. 2007 12:40
Typ studia: Informatika Mgr.

Re: RSA, co delam spatne

Příspěvek od Donarus »

99^7 mod 143 = 44
10^7 mod 143 = 10
51^7 mod 143 = 116
...

pošlu jako

|044|010|116|...etc...
toto pokud ten algoritmus chapu spravne take neni mozne, nebot jak rikam ... kdyz kodujes dvojci, tak bys to mel zakodovat do dvojce ... pokud ne, tak jsem na to nikde v materialech nenarazil... chtelo by to nejakej zdrojak na to kodovani, jenze tam se zas budeme pohybovat v realnem RSA, cili kolem tech 1000 2000 cifer a z toho zas moc nevykoukame :/ a kdyz bych to pak chtel upravit, tak tam zas muzu nasekat tuhletu chybu a bude to k nicemu.. nikde jsem nenasel kvalitni zdrojak, z ktereho by se to dalo vycist ..


EDIT: jenze to co jsem tu ted nahore napsal tak si trosku protireci s modularni aritmetikou :/ OMG
Odpovědět

Zpět na „TIN061 Algoritmy a datové struktury II“