已知 (F_{11}) 上的椭圆曲线 (E : y ^2 = x ^3 + x + 6), 以及 (E) 上的有理点群
(E(F_{11} ) =) { (O,(2,7),(5,2),(8,3),(10,2),(3,6),(7,9),(7,2),(3,5),(10,9),(8,8),(5,9),(2,4))}
手工推算出一段 (Dual-EC-DRBG) 伪随机数样本序列（在此我们不涉及安全性问题），自己设定参数。
概念回顾
(11)的二进制数为(1011)，即这里的(p)为(4)
(R=(x,y)∈E) 则记 (χ (R)=x) (横坐标，视为整数，这里是(4)比特)
(Trunc(x,m))表示(x)的低(p-m)比特
参数选取
取种子(S_0 = 4(0100))
取(m = 2)
推算过程
(E(F_{11} ))={ (O,(2,7),(5,2),(8,3),(10,2),(3,6),(7,9),(7,2),(3,5),(10,9),(8,8),(5,9),(2,4))}
倍点计算后面再说，这里直接写结果了。
(P(2,7) Q(5,2))
输出随机数(Trunc(χ (S_0Q),m) = Trunc(χ (4*(5,2)),m) = Trunc(0011,2))
取(0011)的低(2)比特即输出(11)
更新(S_1 = χ (S_0P) = 10)
(P(8,3) Q(10,2))
输出随机数(，Trunc(χ (S_1Q),m) = Trunc(χ (10*(10，2),m) = Trunc(0010,2))
取(0010)的低(2)比特即输出(10)
更新(S_2 = χ (S_1P) = 10)
(P(3,6)Q(7,9))
输出随机数(Trunc(χ (S_2Q),m) = Trunc(χ (10(7,9)),m) = Trunc(0011,2))
取(0011)的低(2)比特即输出(11)
更新(S_3 = χ (S_2P) = 5)
(P(7,2)Q(3,5))
输出随机数(Trunc(χ (S_3Q),m) = Trunc(χ (5*(3,5)),m) = Trunc(0010,2))
取(0010)的低(2)比特即输出(10)
更新(S_4 = χ (S_3P) = 10)
(P(10,9)Q(8,8))
输出随机数(Trunc(χ (S_4Q),m) = Trunc(χ (10*(8,8)),m) = Trunc(1010,2))
取(1010)的低(2)比特即输出(10)
更新(S_5 = χ (S_4P) = 2)
(P(5,9)Q(2,4))
输出随机数(Trunc(χ (S_5Q),m) = Trunc(χ (2*(2,4)),m) = Trunc(0101,2))
取(0101)的低(2)比特即输出(01)
则推算出 (Dual-EC-DRBG) 序列为(111011101001)
倍点计算举例
已知(G(2,7))在上述椭圆曲线上，求(2G)。
步骤：求(G)与曲线相切时的斜率（求导），得到直线方程；将直线方程代入曲线方程，解三次方程。
计算时注意(P+Q)并不在(PQ)上，而是在(-PQ)上。
设(P(x_1,y_1)Q(x_2,y_2)R(x_3,y_3)) 椭圆曲线(y^2 = x^3+ax+b)
(PQ)斜率：
(K = frac{y_2-y_1}{x_2-x_1}) (P≠Q)
(K = frac{3x^2+a}{2y}) (P=Q)
此时我们算的是(2G)即(P = Q)化简可得(y_3 = kx_3 + C)
将(y_3)代入椭圆曲线方程解得
(y_3 = k(x_1-x_3)-y_1)
(x_3 = k^2 - x_2 -x_1)
将(G(2,7))代入解得(K = frac{12+1}{2x7} = frac{13}{14} mod11)
关于分数求模可参考链接 https://wenku.baidu.com/view/6f2879cca1c7aa00b52acb5f.html
解得(K= 8)，代入 ((x_3,y_3)) 可得 (2G) 为 ((5,2))
倍点计算代码展示
参考链接 https://wenku.baidu.com/view/5e2cce4d767f5acfa1c7cd3b.html
import java.io.*;
public class ecc{
public static int x,y,n,a,p;
public static int getX(int x)
{
int i=1;
while(true)
{
if(modP(x*i)==1)
{
break;
}
i++;
}
return i;
}
public static int modP(int x)
{
if(x<0)
{
while(x<0)
{
x=x+p;
}
}
else
x=x%p;
return x;
}
public static void getR()
{
int X=x,Y=y;
for(int i=1;i<n;i++)
{
if(X==x&Y==y)
{
int k=getK(a,x,y);
X=modP(k*k-x-X);
Y=modP(k*(x-X)-y);
}
else
{
int k=getk(x,y,X,Y);
X=modP(k*k-x-X);
Y=modP(k*(x-X)-y);
}
}
System.out.println("("+X+","+Y+")");
}
public static int getK(int a,int x,int y)
{
int k=(3*x*x+a)*getX(2*y);
return modP(k);
}
public static int getk(int x1,int y1,int x2,int y2)
{
int k=(y2-y1)*getX(x2-x1);
return modP(k);
}
public static void main(String args[]) throws IOException
{
BufferedReader f=new BufferedReader(new InputStreamReader(System.in));
System.out.println("按如下格式输入要计算的倍点：");
System.out.println("椭圆曲线方程：y^2=aX^3+bx+c,请输入：a");
String s=f.readLine();
a=Integer.parseInt(s);
System.out.println("所求坐标Q（x,y），输入x,y");
s=f.readLine();
x=Integer.parseInt(s);
s=f.readLine();
y=Integer.parseInt(s);
System.out.println("输入素数p");
s=f.readLine();
p=Integer.parseInt(s);
System.out.println("倍点nQ，输入n");
s=f.readLine();
n=Integer.parseInt(s);
System.out.println("点Q("+x+","+y+")的"+n+"倍点结果"+n+"Q是");
getR();
}
}