kryptografia.pdf

Kryptogra aklasycznaikwantowa-

laboratorium

1Listazada«

•Szyfrowanieideszyfrowaniemetod¡XOR.

•KryptoanalizaszyfruXOR(kryptoanalizastatystyczna).

•Szyfrystrumieniowe(BlumBlumShub,CBC,OFBiCFB).

•Sprawdzanie,czydanaliczbajestliczb¡pierwsz¡.

•Kryptogra awJavie:JSSE,SSL.

•Implementacjaalgorytmuszyfruj¡cegozkluczempublicznymRSAlub

implementacjaalgorytmuszyfruj¡cegozkluczemtajnymDSA.

•Symulacjakwantowegoalgorytmuuzgadnianiakluczakryptogra cznego

BB84

2Punktacjaiwarunkizaliczenia

Zazadania1−3mo»naotrzyma¢maksymalnie10pn.Zazadania4−7

mo»naotrzyma¢maksymalnie15pn. Š ¡czniemo»naotrzyma¢maksymalnie

60 pn.Punktys¡p rzeliczanenaocenywg.nastƒpuj¡cejtabelki:

0-45ndst

46-54dst

55-63dst+

64-72db

73-81db+

82-90bdb

Zadania1−3rozwiazywanes¡wtrakciezajƒ¢laboratoryjnych,pozosta“e

zadaniamo»narozwi¡zywa¢wdomuioddawa¢wtrakciezajƒ¢laborato-

ryjnychdoko«casemestru.Imszybciejtymlepiej.Zpocz¡tkiemsesji

mijaterminoddawaniazada«.Potymterminiezadanianiebƒd¡

przyjmowane.Dodatkowoprosi“bympozaliczeniuzadaniaoprzes“anie

kodunaadres:lczekaj@mif.pg.gda.pl.Wtemaciewiadomo–ciproszƒumie–-

ci¢napis:"KRPTOGRAFIA".

3Obliczeniawpier–cieniu Z n

1.Podstawy:

abmodn,amod=bmodn,n||(a−b),9 q2 Z nq=a−b(1)

2.Wykonywanieoblicze«

Zde nicjipier–cienia Z n wynikapoprawno–¢nastƒpuj¡cychdzia“a«

(jakoznakmoulo-resztyzdzielenia-bƒdziemypisa¢%zgodniez

konwencj¡jƒzykaC):

(a+b)%n=(a%n+b%n)%n (2)

0=15%3=(7+8)%3=(7%3+8%3)%3=(1+2)%3=0 (3)

(a−b)%n=(a%n−b%n)%n=(a%n+(k·n−b)%n)%n(4)

1=(7−6)%8=(7%8−6%8)%8=(7+(8−6)%8)%8==9%8=1(5)

(a·b)%n=(a%n·b%n)%n (6)

((a+b)·c)%n=((a·c)%n+(b·c)%n)%n (7)

Zachodzir ó wnie»przemienno–¢oraz“¡czno–¢dodawaniaimno»enia.

3.AlgorytmEuklidesadowyznaczaniaNWD(r 0 ,r 1 )(zak“adamy,»er 0

r 1 ):

r 0 =q 1 r 1 +r 2 , (8)

r 1 =q 2 r 2 +r 3 , (9)

r 2 =q 3 r 3 +r 4 , (10)

. . . (11)

r m−2 =q m−1 r m−1 +r m , (12)

r m−1 =q m r m . (13)

JakowynikprzyjmujemyNWD(r 0 ,r 1 )=r m .Je–lir m =1m ó wimy,»e

liczbys¡wzglƒdniepierwsze.

Przyk“ad:NWD(38,16)

38=2·16+6, (14)

16=2·6+2, (15)

6=3·2. (16)

OstatecznieNWD(38,16)=2

4.Wyznaczaniea −1 w Z n .

Niechq j maj¡warto–cijakztwierdzeniaEuklidesa.Zde niujmynastƒpu-

j¡cyci¡grekurencyjny:

t 0 =0 (17)

t 1 =1 (18)

t j =(t j−2 −q j−1 t j−1 )modr 0 (19)

Je»eliNWD(r 0 ,r 1 )=1w ó wczasa −1 =t m .

Przyk“ad:obliczymy28 −1 mod75

AlgorytmEuklidesa:

75=2·28+19 (20)

28=1·19+9 (21)

19=2·9+1 (22)

9=9·1 (23)

Obliczamyt m :

t 0 =0 (24)

t 1 =1 (25)

t 2 =(0−2·1)mod75=73 (26)

t 3 =(1−1·73)mod75=3 (27)

t 4 =(73−2·3)mod75=67 (28)

Ostatecznie28 −1 mod75=67

4Szyfrowanieideszyfrowaniemetod¡XOR

FunkcjaXOR:

aba^b

000

101

011

110

KluczKiwiadomo–¢Mstanowi¡ci¡gibajt ó w.Niechd“ugo–¢klucza

wynosinbajt ó w,w ó wczasszyfrowaniei-tegobajtuwiadomo–cimaposta¢:M i

XORK imodn =C i .Przydeszyfrowaniuwykorzystujemynastƒpuj¡c¡w“as-

no–¢operacjiXOR:AXORBXORB=A.

Wzadaniutymnale»ynapisa¢programszyfruj¡cy/deszyfruj¡cypodany

plikzapomoc¡szyfruXOR.Parametryprogramu:nazwaplikuwej–ciowego,

nazwaplikuwyj–ciowego,klucz(u»ytkownikmo»eokre–li¢d“ugo–¢klucza).

Plikwej–ciowymo»emie¢dowolnyformat.Mo»etoby¢pliktekstowy,jpg,

archiwumetc.Nale»yzwr ó ci¢uwagƒczyplikwej–ciowy/wyj–ciowyjest

otwieranywtrybiebinarnym.Trybbinarnynieoznacza,»enawe-

j–ciuspodziewamysiƒtylkosymboli0i1lub»eplikwej–ciowy

przekszta“camynaci¡gsymboli0i1.

Przydatnekawa“kikodu:

•OperacjaXORwjƒzykuC.

out=a^b

•Otwieraniestrumieniadoodczytubinarnegozpliku.

FILE*f=fopen(nazwa,"rb");

•Otwieraniestrumieniadozapisubinarnegodopliku.

FILE*f=fopen(nazwa,"w+b");

•Odczytci¡gubajt ó wzplikudotablicy.

fread(tablica,1,n,f);

•Zapisci¡gubajt ó wztablicydopliku.

fwrite(tablica,1,n,f);

5KryptoanalizaszyfruXOR(kryptoanalizastatysty-

czna).

Zak“adamy,»eznamyproceduryszyfruj¡ceideszyfruj¡ce.Celematakujest

uzyskanieklucza.Zak“adamy»ekluczjestdu»omniejszyni»kryptogram.

Wybranetypyatak ó w:

•Zsamymkryptogramem(niewiemynicpozatre–ci¡pods“uchanego

kryptogramu).

•Zeznanymtekstemjawnym(opr ó czpods“uchanegokryptogramudys-

ponujemyodpowiadaj¡cymmutekstemjawnym).

•Zwybranymtekstemjawnym(mamydostƒpdokryptogramudowolnie

wybranegotekstujawnego,np.wykradli–myurz¡dzenieszyfruj¡ce).

•Zwybranymkryptogramem(mamydostƒpdotekstujawnegodowol-

negokryptogramu,np.dysponujemyurz¡dzeniemdeszyfruj¡cym).

Kryptoanalizastatystycznabazujenanier ó wnomiernymrozk“adzieliter

isylabjƒzykanaturalnegooraznainnychznanychaprioristatystycznych

cechachtekstujawnego.Nat¡metodƒkryptoanalizyszczeg ó lniewra»liwe

s¡wszystkieszyfrypodstawieniowe,wszczeg ó lno–ciszyfryXOR.Niechu»y-

wanyprzeznasszyfrpodstawieniowyzamieniaznaka i naznakb i .W ó wczas

czƒstotliwo–¢wystƒpowaniaznakub i wkryptogramieodpowiadaczƒstotli-

wo–ciwystƒpowaniaznakua i wtek–ciejawnym.

Jakoprzyk“adwe„myjƒzykABC.NiechliteraAwystƒpujeznajwiƒk-

szymprawdopodobie«stwem,za–literaCznajmniejszym.Niechkryptogram

"ABBBBBABBBBBBABBBBBABBBBBAABBBBCBB"bƒdziereprezentaty-

wnymzdaniemztegojƒzykazaszyfrowanymzapomoc¡szyfrupodstaw-

ieniowego.Mo»nabeztruduodgadn¡¢»eszyfrowaniepoleganazamianie

literAiB.

Czƒstotliwo–¢wystƒpowanialiterwjƒzykuangielskim:

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika: