crypto常用工具

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/