Mathematik 3  fuer CMS,FHS Hagenberg
12. Uebungsblatt fuer den 10.1.2006

Nehmen Sie bitte Ihre Loesungen auf USB-Stick in die Uebungen mit.

Setup

<< Algebra`PolynomialPowerMod`

RandomPoly[var_, degree_, p_] := 
      Sum[Random[Integer, {0, p - 1}] var^i, {i, 0, 
          degree}]


IrreducibleQ[f_, p_] := 

  

(Factor[f, Modulus -> p] === 
          f)


PrimitiveQ[w_, f_, var_, 
          p_] := 

 (* 
          returns True if the element w from the field
Z_p[var]/f is primitive,  
          returns False otherwise *) 

Module[{size, factors, n, i, 
            canStillBePrimitive, r}, 
size = 
            p^Exponent[f, var]; 
factors = 
            FactorInteger[size - 1]; 
n = 
            Length[factors]; 
i = 
            1; 
canStillBePrimitive = 
            True; 
While[
            canStillBePrimitive  && 
              i <= n, 
r = (size - 
                    1)/factors[[i]][[1]]; 
canStillBePrimitive  = (PolynomialPowerMod[w, 
                    r, {f, p}] =!= 1); 
i  =  
              i + 1]; 
canStillBePrimitive];

12.1 und 12.2

Bestimmen Sie ein primitives Element in einem Koerper ihrer Wahl mit 2^128 Elementen. Verwenden Sie obige Funktionen.

Wieviele Polynome mussten Sie testen, bis Sie ein irreduzibles vom passenden Grad fanden?
Wieviele Polynome mussten Sie testen, bis Sie ein primitives Element fanden?

Loesung

12.3

Gegeben ist der Koerper K = Z_2[x]/f.

f = 
        1 + x + (x^5) + (x^7) + (x^8) + (x^9) + (x^10) + (x^11) + (x^12) + (x^15) + 
          (x^16) + (x^18) + (x^19) + (x^20) + (x^21) + (x^26) + (x^28) + (x^29) + 
          (x^30) + (x^31) + (x^32) + (x^33) + (x^38) + (x^39) + (x^43) + (x^50) + 
          (x^51) + (x^53) + (x^54) + (x^62) + (x^63) + (x^64) + (x^65) + (x^70) + 
          (x^72) + (x^73) + (x^76) + (x^79) + (x^82) + (x^83) + (x^85) + (x^86) + 
          (x^88) + (x^90) + (x^92) + (x^93) + (x^94) + (x^96) + (x^98) + (x^100) + 
          (x^102) + (x^103) + (x^105) + (x^108) + (x^109) + (x^110) + (x^114) + 
          (x^117) + (x^120) + (x^124) + (x^128);

Fuer die multiplikative Gruppe von K haben Sie den privaten ElGamal-Schluessel

a = 207963635422861161657423029393164330002;

und den oeffentlichen Schluessel mit dem erzeugenden Element

alpha = x^2 + x^6;
y = PolynomialPowerMod[alpha, a, {f, 2}];

Unterschreiben Sie die Nachricht m, wobei Sie die fingierten Hashwerte
h(m) = m und h(r) = 123456789 verwenden.

m = 34022966960451826625355775704067793276;

Loesung:

12.4

Sei K und alpha wie in Aufgabe 3. 
Verifizieren Sie die Unterschrift (r,s) der Nachricht m mit dem oeffentlichen ElGamal-Schluessel (alpha, y).
(Verwenden Sie die fingierten Hashwerte h(m) = m und h(r) = 987654321).

y = 
        (x^2) + (x^3) + (x^4) + (x^6) + (x^7) + (x^8) + (x^10) + (x^11) + (x^13) + 
          (x^14) + (x^16) + (x^17) + (x^18) + (x^20) + (x^21) + (x^23) + (x^26) + 
          (x^32) + (x^33) + (x^34) + (x^35) + (x^38) + (x^39) + (x^40) + (x^41) + 
          (x^43) + (x^50) + (x^51) + (x^52) + (x^55) + (x^56) + (x^59) + (x^60) + 
          (x^63) + (x^65) + (x^66) + (x^70) + (x^74) + (x^75) + (x^76) + (x^77) + 
          (x^84) + (x^87) + (x^89) + (x^91) + (x^93) + (x^94) + (x^97) + (x^98) + 
          (x^99) + (x^100) + (x^102) + (x^105) + (x^107) + (x^110) + (x^112) + 
          (x^116) + (x^117) + (x^121) + (x^123) + 
          (x^124);

m = 
        8739565232515543365321593053148161493;

r = 
        1 + x + (x^3) + (x^6) + (x^9) + (x^10) + (x^12) + (x^17) + (x^18) + (x^19) + 
          (x^20) + (x^23) + (x^24) + (x^25) + (x^27) + (x^28) + (x^30) + (x^31) + 
          (x^34) + (x^35) + (x^36) + (x^38) + (x^40) + (x^41) + (x^42) + (x^45) + 
          (x^46) + (x^47) + (x^48) + (x^49) + (x^50) + (x^51) + (x^52) + (x^53) + 
          (x^54) + (x^59) + (x^60) + (x^61) + (x^62) + (x^65) + (x^67) + (x^69) + 
          (x^71) + (x^72) + (x^74) + (x^76) + (x^77) + (x^79) + (x^82) + (x^85) + 
          (x^87) + (x^88) + (x^89) + (x^91) + (x^93) + (x^96) + (x^98) + (x^100) + 
          (x^103) + (x^104) + (x^105) + (x^109) + (x^110) + (x^111) + (x^113) + 
          (x^114) + (x^115) + (x^116) + (x^118) + (x^121) + (x^122) + (x^124) + 
          (x^125) + (x^126);

s = 22594439109307123752023200670798033018;

Loesung:

12.5

Warum reicht es beim ElGamal-Signatur-Schema nicht, (k,s) statt (r,s) als Unterschrift zu verwenden?