crypto常用工具

常用工具

  • 古典密码

  • gmpy2

    1
    2
    3
    4
    5
    6
    7
    8
    9
    import gmpy2
    gmpy2.mpz(n) #初始化一个大整数
    gmpy2.mpfr(x) # 初始化一个高精度浮点数x
    d = gmpy2.invert(e,n) # 求逆元,de = 1 mod n
    c = gmpy2.powmod(m,e,n) # 幂取模,结果是 c = m^e mod n
    gmpy2.is_prime(n) #素性检测
    gmpy2.gcd(a,b) #欧几里得算法,最大公约数
    gmpy2.gcdext(a,b) #扩展欧几里得算法
    gmpy2.iroot(x,n) #x开n次根

  • Sage

    定义

    1
    2
    3
    4
    5
    6
    R.<X> = PolynomialRing(Zmod(n))
    #Zmod(n):指定模,定义界限为n的环;Z表示整数;指定模是划定这个环的界限,就是有效的数字只有从0到n,其他的都通过与n取模来保证在0~n这个范围内;Zmod代表这是一个整数域中的n模环
    #ZZ:整数环;QQ:有理数环;RR:实数环;CC:复数环
    #R:只是一个指针,指向用polynomialring指定的那个环(可以使用任意字符)
    #PolynomialRing:这个就是说建立多项式环
    #.<X>:指定一个变量的意思(可以用任意字符)

    解方程

    $\begin{cases} x+y=10\\xy=21 \end{cases} $

    1
    2
    var('x y')
    solve([x+y==10,x*y==21],[x,y])

    解线性方程组

    $AX=B$

    1
    2
    3
    4
    5
    6
    A = Matrix([[1,2,3],[3,2,1],[1,1,1]]) 
    Y = vector([0,-4,-1])
    X = A.solve_right(Y)
    #或
    A \ Y
    #反斜杠 \ 可以代替 solve_right; 用 A \ Y 代替 A.solve right(Y).

    求逆元

    $ed=1\pmod {\varphi(n)}$

    1
    d = inverse_mod(e,fn) # sage求逆元

    扩展欧几里得算法

    1
    2
    d,u,v=xgcd(20,30)
    print("d:{0} u:{1} v:{2}".format(d,u,v)) #d:10 u:-1 v:1

    CRT(中国剩余定理)

    $\begin{cases} x\equiv2\pmod3\\x\equiv3\pmod5\\x\equiv2\pmod7 \end{cases} $

    1
    crt([2,3,2],[3,5,7])
    1
    2
    3
    4
    5
    6
    7
    8
    9
    #仅适用模两两互素
    def chinese_remainder(modulus, remainders):
    Sum = 0
    prod = reduce(lambda a, b: a*b, modulus)
    for m_i, r_i in zip(modulus, remainders):
    p = prod // m_i
    Sum += r_i * (inverse_mod(p,m_i)*p)
    return Sum % prod
    chinese_remainder([3,5,7],[2,3,2]) #23

    离散对数

    $2^x \equiv 13 \pmod {23}$

    1
    2
    x = discrete_log(mod(13,23),mod(2,23))
    print(x)

    欧拉函数

    $\varphi(x)=x\prod\limits_{i=1}^n(1-\frac{1}{p_i})$

    1
    print(euler_phi(71)) #70

    创建整数域中的椭圆曲线

    $y^2=x^3+a_4x+a_6$

    输出所有整数点

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
      #素数域
    F = GF(7)
    #素数域的阶
    print(F.order())
    #椭圆曲线E7(2,3)
    E = EllipticCurve(F,[0,0,0,2,3])
    #基点坐标
    G = E.gens()[0]
    #阶
    q = E.order()
    #所有的点
    allPoints = E.points()
    #创建点
    P = E(2,1)

    参考:

    https://jayxv.github.io/2020/05/20/sage%E5%B8%B8%E7%94%A8%E5%91%BD%E4%BB%A4/

  • WolframAlpha

    https://www.wolframalpha.com/