|
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; |
|