V předmětu Algoritmizace jsme během roku dostávali rozličné domácí úkoly, které se v posledním úkolu důmyslně poskládaly a vzniklo jednoduché RSA šifrování. Takové RSA šifrování je založeno na jednoduchém principu, a to že libovolné číslo se dá přepsat jako součin prvočísel. Součin prvočísel je elementární úloha, která zabere běžnému počítači malé zlomky tisíciny vetřiny, naopak rozklad čísla (zejména velkého) na součin prvočísel je úloha velice složitá a pro hodně velká čísla téměř neproveditelná v rozumném čase.
Je třeba vytvořit pár klíčů (uspořádané dvojice čísel) – veřejný klíč a soukromý klíč. Klíče se vytvoří takto: Zvolí se dvě náhodná prvočísla a určí se jejich součin n a hodnota Eulerovy funkce v tomto bodě – φ(n) jako (p – 1) * (q – 1). Zvolí se celé číslo e nesoudělné s φ(n) menší než φ(n), tak aby platilo de ≡ 1 (mod φ(n)) a jestli e je prvočíslo tak d = (1+r*φ(n))/e, kde r = [(e-1)φ(n)^(e-2)]. Opsal jsem to z wikipedie, protože jsem to sám pořádně nepochopil :-).
Zajímavá věc je ale šifrování samotné. Nedělá v podstatě nic jiného, než že převádí informace na jiné informace podle určitého jednoznačného systému, přičemž tento proces je vratný. V podstatě tedy nedělá nic jiného, než že nasazuje na informace jakousi masku, přes kterou nepoznáme, o co se jedná. Souvislost a podstata informací se ale nemění. Kdyby lidstvo od pradávna žilo v číslech, dešifrování určité sady čísel či přinejmenším pochopení podstaty skrytých informací by nám nedělalo tak podstatný problém. Nechte mě toto tvrzení dokázat.
Lidé většinou nevidí svět v číslech, ale v obrazech. Body určité barvy, jako základní složky obrazů, se ale dají převést na čísla, tudíž i zašifrovat. Barevná rozlišovací schopnost lidí je mi neznámá, zdaleka však není stoprocentní, to znamená, že člověk má tendenci dvě barvy změněné o nepatrný odstín považovat za stejné. Empiricky se přišlo na to, že člověk už nepozná rozdíl mezi 24bitovým obrázkem a obrázkem vyšší kvality… berme tedy rozlišovací schopnost lidského oka jako 24 bitů.
A není náhodou, že zde zrovna jeden obrázek ve 24 bitovém rozlišení mám. Celkem hezký.
Nevím, jak se slečna jmenuje, ale dovolím si ji vypůjčit k malému experimentu. Proženeme její část mým RSA šifrovacím algoritmem a podíváme se, jak moc se slečna zmení… jestli stále ještě dokážeme poznat, že se jedná o slečnu.
To, co prosím vidíte je částečně zašifrovaný obrázek. Zašifrovaná data (určitě poznáte, o která se jedná) by nemělá být ani v nejmenším čitelná běžným pohledem. A kdyby šlo o čísla nebo o znaky, také by čitelná nebyla. Protože však žijeme ve světě obrazů již od malička a náš mozek, jak známo – nejdokonalejší počítač, v obrazech pracuje, dokáže vcelku snadno zachytit v šifrovaných informacích určitou pravidelnost a odhalit tak podstatu šifrovaných informací. Zjistíme, že se jedná o slečnu, přinejmenším o člověka.
Platí pravidlo, že čím jednoduší jsou šifrovaná data, tím jednodušeji je lze dešifrovat. To ve světě obrazů platí dvojnásob. Pokud převedeme slečnu ze světa 24bitů do 256 barev (což byla kdysi velice slušná kvalita digitálního zpracování obrazů),
zjistíme, že šifrovaný obrázek přečteme mnohem snadněji.
V tomto případě zjišťujeme přesně fakt, že se jedná o slečnu a že je pěkná. Lidé s rozvinutějším mozkem v určitých oblastech (třeba někteří autisté) by poznali i o koho se jedná. Pokud slečnu zjednodušíme na pouhých 16 barev,
poznáme i my zaostalejší, o koho jde.
Což je docela dobré na to, že informace má být nečitelná. Mimochodem, já nevím, o koho jde i přes to, že mi to přítelkyně několikát říkala. Narazil jsem na ni na Okounovi a od té doby ji zneužívám k různým bitovým hrátkám.
Člověk je ale relativně zvyklý přemýšlet i ve slovech, nebo ne? Avšak dešifrovaní věty v jeho rodném jazyce jakkoli jednoduchou šifrou (natož RSA) mu dělá značný problém. Kdyby mi někdo poslal velmi krátkou smysluplnou větu sestávájící z písmen abecedy zašifrovanou pomocí RSA, troufnu si tvrdit, že bych na základě znalostí větné stavby a stavby slov, dokázal odhalit něco kolem 50 až 75 procent její podstaty. Trvalo by mi to ale minimálně den. Kdyby mi někdo poslal smysluplná čísla, ve kterých lidé nepřemýšlí, neodhalil bych jejich podstatu nikdy, narozdíl od počítače. Někteří autisté slovní a číselné šifry prokouknou stejně snadno jako my ty obrazové… dokážete si představit, jak dokonalý musí být lidský mozek? Není čas začít přemýšlet o návratu k analogové technice :-)?
Pokud si chcete bitové hrátky s RSA šifrou také vyzkoušet, dám k disposici kód v jazyce Java.
import java.io.*;
public class KlicRSA
{
private long N
;
private long k
;
public KlicRSA
(long N,
long k
) throws Exception
{
if(N
< 256
|| N
> 32767
)
{
throw new Exception("<256;32767>");
}
this.
N = N
;
this.
k = k
;
}
private static long umocni
(long a,
long b,
long n
)
{
long ret
= 1;
for(long i
= Long.
highestOneBit(b
); i
> 0; i
>>= 1
)
{
if((b
& i
) != 0
)
{
ret
= (ret
* a
) % n
;
}
if(i
> 1
)
{
ret
= (ret
* ret
) % n
;
}
}
return ret
;
}
public void zasifrujSoubor
(String zdroj,
String cil
)
throws java.
io.
IOException
{
DataInputStream dis
= new DataInputStream(new
FileInputStream(zdroj
));
DataOutputStream dos
= new DataOutputStream(new
FileOutputStream(cil
));
int b
;
while(dis.
available() != 0
)
{
b
= dis.
readUnsignedByte();
dos.
writeShort((short) umocni
(b,
this.
k,
this.
N));
}
dis.
close();
dos.
close();
}
public void zasifrujKus
(String zdroj,
String cil
)
throws java.
io.
IOException
{
DataInputStream dis
= new DataInputStream(new
FileInputStream(zdroj
));
DataOutputStream dos
= new DataOutputStream(new
FileOutputStream(cil
));
byte b
;
long i
= 0;
while(dis.
available() != 0
)
{
b
= dis.
readByte();
if((i
> 10000
) && (i
< 20000
))
{
dos.
writeByte((byte) umocni
(b,
this.
k,
this.
N));
}
else
{
dos.
writeByte(b
);
}
i
++;
}
dis.
close();
dos.
close();
}
public void desifrujSoubor
(String zdroj,
String cil
)
throws java.
io.
IOException
{
DataInputStream dis
= new DataInputStream(new
FileInputStream(zdroj
));
DataOutputStream dos
= new DataOutputStream(new
FileOutputStream(cil
));
short s
;
while(dis.
available() != 0
)
{
s
= dis.
readShort();
dos.
writeByte((byte) umocni
((int) s,
this.
k,
this.
N));
}
dis.
close();
dos.
close();
}
}
Já jsem používal klíče (1469, 5) a (1469, 269).
