椭圆曲线密码题计算器

发表于 更新于 分类于
做密码学算术题用的。

椭圆曲线密码题计算器

第4章 公钥密码体制.ppt 下载

求逆元

扩展欧几里得算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def gcd(m, n):
    """辗转相除判断互素"""
    while m != 0:
        m, n = n % m, m
        return n
    
def ex_gcd(a, mod):
    """扩展欧几里德算法，算术法"""
    if gcd(a, mod) != 1:
        return None
    u1, u2, u3 = 1, 0, a
    v1, v2, v3 = 0, 1, mod
    while v3 != 0:
        q = u3 // v3
        v1, v2, v3, u1, u2, u3 = (u1 - q * v1), (u2 - q * v2), (u3 - q * v3), v1, v2, v3
        return u1 % mod

椭圆曲线求值

求p,2p,3p…到O的值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
def get_niyuan(sum:int, mod:int=11)->int:
    """
    暴力法求逆元
    sum:值
    mod：模
    """
    result = 0
    while sum*result % mod != 1:
        result += 1
    return result

def get_circle(x1:int=2, y1:int=7, circle:int=12, a:int=1, mod:int=11)->None:
    """
    x1,x2：本原根，
    circle：O的离散对数，未知可以将circle值调大，程序算到O时卡死,此时|E|等于最后算出的P+1
    y2=x3+ax+b mod n   
    a就是这里的a，mod是这里的n  
    """
    x2, y2 = 0, 0
    x3, y3 = 0, 0
    i = 1
    print("本原根("+str(x1)+","+str(y1)+"),O的离散对数"+str(circle)+",方程式a的值"+str(a)+",模"+str(mod))
    while i < circle:
        if i == 1:
            lamda = ((3*(x1**2)+a)*get_niyuan(2*y1, mod)) % mod
            x2 = x1
            y2 = y1
        else:
            lamda = (y2-y1)*get_niyuan(x2-x1, mod) % mod
        x3 = (lamda**2-x1-x2)%mod
        y3 = (lamda*(x1-x3)-y1)%mod
        print(str(i+1)+"p\tlamda="+str(lamda)+" \t(",x3,",",y3,")")
        i+=1
        x2 = x3
        y2 = y3
get_circle(2,7,12)
print('\n')
get_circle(8, 3, 12)
print('\n')
get_circle(10,9,12)