B csop. Kriptogr\303\241fia II. ZHQyhJJE58ZHdWRzYiISIiKiZJJEVUUkdGJCIiIkkqYXpvbm9zfGh5dHxeekdGJEYoRiVJJGd8ZHlwR0YkRiU=1. a) Mi az RC4?Az RC4 folyamtitkos\303\255t\303\263 algoritmus, az \303\274zenetet bitenk\303\251nt k\303\263dolja egy \303\241lv\303\251letlen kulcsfolyam gener\303\241l\303\241s\303\241val, biztons\303\241gosnak tartj\303\241k, nagyon gyors.b) Mire szolg\303\241l a digit\303\241lis al\303\241\303\255r\303\241s?
A digit\303\241lis al\303\241\303\255r\303\241sa az \303\274zenet s\303\251rtetlen\303\251g\303\251nek meg\303\241llap\303\255t\303\241s\303\241ra, a felad\303\263 szem\303\251ly\303\251nek hiteles\303\255t\303\251s\303\251re \303\251s a k\303\274ld\303\251s letagadhatatlans\303\241g\303\241ra szolg\303\241l.2. Tegy\303\274k fel, hogy egy (n,e) nyilv\303\241nos kulcssal titkos\303\255tott \303\274zenthez tudom\303\241sunkra jutott a \317\225(n) titkos \303\251rt\303\251k is. Ez alapj\303\241n t\303\266rj\303\274k fel a titkos\303\255t\303\241st, vagyis sz\303\241m\303\255tsuk ki a felad\303\263 (n,d) mag\303\241nkulcs\303\241t, \303\251s fejts\303\274k meg a C titkos\303\255tott \303\274zenetet! Sz\303\241m\303\255tsa ki az n k\303\251t pr\303\255mt\303\251nyez\305\221j\303\251t is, f1-et \303\251s f2-t! A nyilv\303\241nmos kulcs exponens\303\251t a szok\303\241sos d v\303\241ltoz\303\263ba, a ny\303\255lt sz\303\266veg k\303\263dj\303\241t az M v\303\241ltoz\303\263ba mentse!n := 71176979405477373830445679092411325180653454455273724489111633279535410516450353951525739815352474104430023265992596635126379473788211011715193926600888060816489284748967003910688272568762647237688301;e := 69880398186280805217524969048205618745460051289275411934129680161749970681523302079975730040521592669058534275392408405176274590669927863669249183279957415309819169347194138280155001550732550779670373;phien:=71176979405477373830445679092411325180653454455273724489111633279535410516450353951525739815352474087556131023677736440986098660183262242909833905904712018900860213644294159689678497668937341051984704;C := 987654321;
solve([f1*f2=n,(f1-1)*(f2-1)=phien]);assign(%);f1;f2;evalb(f1*f2 =n);d:=(1/e mod phien);M:=Power(C,d) mod n;CC:=Power(M,e) mod n;3. Felt\303\251telezve, hogy az m sz\303\241m pr\303\255moszt\303\263i k\303\266zel egyform\303\241k faktoriz\303\241lja m-et! A k\303\251t faktort t\303\241rolja a p1 \303\251s p2 v\303\241ltoz\303\263kban!
QyQ+SSJtRzYiImZuQE06XCFIKCl6dTBRVkFlc0tMZUNIa00oMy0uQSdHLUUiIiI=tt:=isqrt(m);while not issqr(tt^2-m) do tt:=tt+1 end do;rr:=sqrt(tt^2-m);p1:=tt-rr;p2:=tt+rr;isprime(p1);isprime(p2);evalb(p1*p2 = m);4. Az ElGamal kriptorendszert haszn\303\241ljuk, legyenek a nyilv\303\241nos param\303\251terek: egy qq pr\303\255m \303\251s annak a primit\303\255v gy\303\266ke.a) Az A X[A] mag\303\241nkulcs\303\241hoz k\303\251sz\303\255ts\303\274k el , az A nyilv\303\241nos kulcs\303\241t, azaz Y[A]-t!b) Hogyan k\303\274ldheti el ezut\303\241n B az A-nak az M2 \303\274zenetet, ha feltessz\303\274k, hogy ehhez a k v\303\251letlen \303\251rt\303\251ket haszn\303\241lja? A titkos\303\255tott \303\274zenetet t\303\241rolja a C[1] \303\251s C[2] v\303\241ltoz\303\263kban!.
c) Hogyan tudja ezut\303\241n A (tern\303\251szetesen a mag\303\241nkulccsa seg\303\255ts\303\251g\303\251vel) megfejteni az \303\274zenetet? A megfejtett \303\274zenet ker\303\274lj\303\266n M3-ba!
QyQ+SSNxcUc2IiI1LGhZKipHLlknZWEoIiIia:= 11;X[A] := 54616288456346239976;M2:=9876543210;k := 27728937795087420825;
Y[A]:=Power(a,X[A]) mod qq;mask:=Power(Y[A],k) mod qq;C[1]:=Power(a,k) mod qq;C[2]:=mask*M2 mod qq;ujmask:=Power(C[1],X[A]) mod qq;M3:=(1/ujmask mod qq) * C[2] mod qq;5. a) Hat\303\241rozzon meg egy olyan 1024 bites p pr\303\255msz\303\241mot, melyre p-1-nek van egy legal\303\241bb legal\303\241bb 160 bites pr\303\255m oszt\303\263ja, legyen ez q. b) Sz\303\241m\303\255tson ki egy olyan g (1 < g < p) sz\303\241mot melynek a rendje legal\303\241bb q modulo p.
c) V\303\241lasszon egy (1 < X[A] < p) mag\303\241nkulcsot \303\251s k\303\251sz\303\255tse el vele, - egy v\303\251letlen k \303\251rt\303\251kkel, valamint a p, q, g nyilv\303\241nos param\303\251terekkel - a hash hash-k\303\263d\303\272 \303\274zenet DSA al\303\241\303\255r\303\241s\303\241t. T\303\241rolja az al\303\241\303\255r\303\241st az r,s v\303\241ltoz\303\263kban!
hash:=121212121212121212;
q0:=rand(2^159..2^160)();q:=nextprime(q0);t:=rand(2^863..2^864)();
while not isprime(2*t*q+1) do t:=t+1; end do:p:=2*t*q+1;keres:=proc()
local h,g;
h:=rand(1..p)();
g:=Power(h,2*t) mod p;
while g=1 do h:=h+1; g:=Power(h,2*t) end do;
return(g);
end proc;
g:=keres();Power(2,2*t) mod p;x:=rand(1..q)();k:=rand(1..q)();p;q;g;r:=(Power(g,k) mod p) mod q;
s:=1/k*(hash+x*r) mod q;y:=Power(g,x) mod p;w:=1/s mod q;u1:= w*hash mod q;u2:= w*r mod q;v:=(Power(g,u1)*Power(y,u2) mod p ) mod q;evalb(r=v);