格在NTRU例子

cjsh

http://www.ntru.com/tutorials/pkcstutorial.htm 应用数论的最前沿之一 对量子密码传输有攻击希望的NTRU： NTRU 算法需要三个整数参数( N, p, q) 和四个L, L, L, L 具有的N - 1 阶多项式环。在实际应用中为增 加安全性, NTRU 算法要求gcd ( p, q) = 1, 并且p 要远大 于q。 对于f: f ∀ Lf 多项式要求其系数为1 的个数等于df, 而系数为- 1 的个数等于df- 1, 其余系数等于0。 对于g : g ∀ Lg 多项式要求其系数为1 和- 1 的个数 相等, 并且等于dg, 其余的系数等于0。 对于r: r ∀ Lr 多项式要求其系数为1 和- 1 的个数相 等, 并且等于dr , 其余的系数等于0。表1 是NTRU 技术 根据不同的安全级推荐的参数。 表1 N p q d d d 一般安全107 64 3 15 12 5 高安全167 128 3 61 20 18 最高安全503 256 3 216 72 55 Arithmetic will be done in R = Z[X] with reduction modulo XN ¡ 1 for N = 11. We will also need to reduce modulo p = 3 and q = 32. Thus, we create rings Rp = Z[X] =p and Rq = Z[X] =q. > N := 11; > q := 32; > p := 3; > R := PolynomialRing( Integers() ); > Rp := PolynomialRing( GF(p) ); > Rq := PolynomialRing( ResidueClassRing( q ) ); We will need to compute inverses in the ring of truncated polynomials modulo p and q. Algorithms for doing this are given at http://www.ntru.com/tech.technical.htm. Below is an implementation of the algorithms within Magma: function InverseModPrime( R, a, p, N ) X := R.1; Rp := PolynomialRing( GF(p) ); k := 0; b := R!1; c := R!0; f := a; g := X^N - 1; while true do f0 := Evaluate(f, 0); while f0 eq 0 do f := f div X; c := c * X; k +:= 1; f0 := Evaluate(f, 0); end while; if Degree(f) eq 0 then b := R!Rp!(b * Modinv( f0, p ans := b*X^(-k mod N) mod (X^N-1); break; end if; if Degree( f ) lt Degree( g ) then t := f; f := g; g := t; t := b; b := c; c := t; end if; f0 := Evaluate(f, 0); g0 := Evaluate(g, 0); u := (Modinv( g0, p ) * f0) mod p; f := R!Rp!(f - u*g); b := R!Rp!(b - u*c); end while; return ans; end function; function InverseModPrimePower( R, a, prime_power, N ) ok, p, r := IsPrimePower( prime_power ); if ok eq false then print "ERROR: function requires prime power"; return 0; end if; b := InverseModPrime( R, a, p, N ); q := p; X := R.1; while q lt prime_power do q := q*p; Rq := PolynomialRing( ResidueClassRing( q ) ); b := R!Rq!( (b * (2 - a * b)) mod (X^N - 1) ); end while; return b; end function; We take the example polynomials f(X) and g(X) from the web site, and compute ² Fp - the inverse of f in the ring Z[X] =(p;XN ¡ 1) ² Fq - the inverse of f in the ring Z[X] =(q;XN ¡ 1). The results are coerced back to polynomials in Z[X]. It is easy to check that the inverses are correct. The values of Fp, p and g(X) are used to compute the public key h(X). > f := -1+X+X^2-X^4+X^6+X^9-X^10; > g := -1+X^2+X^3+X^5-X^8-X^10; > Fp := InverseModPrimePower( R, f, p, N ); > Fq := InverseModPrimePower( R, f, q, N ); > Fp; 2*X^9 + X^8 + 2*X^7 + X^5 + 2*X^4 + 2*X^3 + 2*X + 1 > Fq; 30*X^10 + 18*X^9 + 20*X^8 + 22*X^7 + 16*X^6 + 15*X^5 + 4*X^4 + 16*X^3 + 6*X^2 + 9*X + 5 > R!Rp!(f*Fp mod (X^N - 1)); 1 > R!Rq!(f*Fq mod (X^N - 1)); 1 > h := R!Rq!(p*Fq*g mod (X^N - 1)); > h; 16*X^10 + 19*X^9 + 12*X^8 + 19*X^7 + 15*X^6 + 24*X^5 + 12*X^4 + 20*X^3 + 22*X^2 + 25*X + 8 To encrypt a message, we represent it as a polynomial having coefficients between ¡p=2 and +p=2, and randomly select a polynomial r(X) having a fixed number of +1 and -1 coefficients. The encryption of m(X) is e(X) = r(X) ¤ h(X) + m(X) mod Z[X] =(q;XN ¡ 1). We use the polynomials m(X) and r(X) from the example on the NTRU web site. > m := -1+X^3-X^4-X^8+X^9+X^10; > r := -1+X^2+X^3+X^4-X^5-X^7; > e := R!Rq!((r*h + m) mod (X^N - 1)); > e; 19*X^10 + 6*X^9 + 25*X^8 + 7*X^7 + 30*X^6 + 16*X^5 + 14*X^4 + 24*X^3 + 26*X^2 + 11*X + 14 Decryption will require adjusting polynomials so that the coefficients are between ¡p=2 and +p=2 or ¡q=2 and +q=2. The following function performs the adjustment. function AdjustPolynomial( R, a, q ) coeffs := Eltseq( a ); qdiv2 := q div 2; for i in [1..#coeffs] do if coeffs gt qdiv2 then coeffs -:= q; end if; end for; return R!coeffs; end function; Finally we can perform the decryption steps and verify that the solution is correct. > a := R!Rq!((f*e) mod (X^N - 1)); > a; 25*X^10 + 29*X^9 + 5*X^8 + 7*X^7 + 6*X^6 + 7*X^5 + 10*X^4 + 21*X^3 + 22*X^2 + 25*X + 3 > a := AdjustPolynomial( R, a, q ); 230 > a; -7*X^10 - 3*X^9 + 5*X^8 + 7*X^7 + 6*X^6 + 7*X^5 + 10*X^4 - 11*X^3 - 10*X^2 - 7*X + 3 > b := AdjustPolynomial( R, R!Rp!a, p); > c := AdjustPolynomial( R, R!Rp!(Fp*b mod (X^N - 1)), p); > c; X^10 + X^9 - X^8 - X^4 + X^3 - 1 > c eq m;

cjsh