7.Uebungsblatt fuer den 18.11.2004

Bsp. 7.1, repeated encryption

n = 232646010703534527043004781508727467783; 
    e = 13540244009200422207061387266821599433; 
    c = 197212580404504151079829847853402100374;

cr = PowerMod[c, e, n]; k = 2;
While[cr =!= c, cr = PowerMod[cr, e, n]; Print[{k, cr}]; 
      k = k + 1 ]

d = e^5

Faktorisation von n aus e und d:

k = e d - 1

t  =  k/16

Waehle a= 2 und verwende die Idee vom quadratischen Sieb:

a = 2;
PowerMod[a, t, n]
PowerMod[a, 2  t, n]
PowerMod[a, 4  t, n]

Also hat a^(2t)-1 einen gemeinsamen Teiler mit n:

p = GCD[n, PowerMod[a, 2  t, n] - 1]

q = n/p

Bsp. 7.2, common modulus

e1 = 17;
c1 = 
        182590323267042430195589196212851511475;
e2 = 257;
c2 = 56682700857331418542105952874843982367;

ExtendedGCD[e1, e2]

-8*257 + 121*17

Berechnen c1^-8 *c2 ^121 = m  (mod n):

coeff = ExtendedGCD[c1, n]

invc1 = Mod[coeff[[2]][[1]], n]

m = Mod[invc1^8*c2^121, n]

Bsp. 7.3, small encryption exponent

c = 1949092844491425267245617011343361024;

m = c^(1/5)

Bsp.7.4, factorization of n from e, d

e = 23011967;
d = 164475374728334378198948086435160402327;

t = e d  - 1

t  =  t/2

t =  t/2

t =  t/2

Waehle a= 2 und verwende die Idee vom quadratischen Sieb:

a = 2;
PowerMod[a, t, n]
PowerMod[a, 2  t, n]
PowerMod[a, 4  t, n]

Also hat a^(2t)-1 einen gemeinsamen Teiler mit n:

p = GCD[n, PowerMod[a, 2  t, n] - 1]

q = n/p