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>：指定一个变量的意思（可以用任意字符）

    ​

    多项式

    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
    f.subs({x:x1}) #把x1值代入x
    f.univariate_polynomial() #映射为单变量多项式
    f.univariate_polynomial().roots() #单变量多项式求根
    f.coefficients() #多项式系数列表
    f.monic() #首一多项式

    #因式分解（单元）
    x = PolynomialRing(RationalField(), 'x').gen()
    f = (x^3 - 1)^2-(x^2-1)^2
    f.factor()

    #因式分解（二元）
    x, y = PolynomialRing(RationalField(), 2, ['x','y']).gens()
    f =  (9*y^6 - 9*x^2*y^5 - 18*x^3*y^4 - 9*x^5*y^4 + 9*x^6*y^2 + 9*x^7*y^3 + 18*x^8*y^2 - 9*x^11)
    f.factor()

    #GCD（单元）
    x = PolynomialRing(RationalField(), 'x').gen()
    f = 3*x^3 + x
    g = 9*x*(x+1)
    f.gcd(g)

    #GCD（多元）
    R.<x,y,z> = PolynomialRing(RationalField(), order='lex')
    f = 3*x^2*(x+y)
    g = 9*x*(y^2 - x^2)
    f.gcd(g)

    ​

    解方程

    $\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
    15
    16
    #素数域
    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)
    #点的xy坐标值
    P.xy()

    ​

    解方程

    $\begin{cases} N=pq \ \varphi = (p-1)(q-1) \end{cases} $

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    P.<p, q> = PolynomialRing(ZZ)
    def solve(f1, f2):
    	g = f1.resultant(f2, q)
    	roots = g.univariate_polynomial().roots()
    	if len(roots) == 0:
    		return False
    	p_ = abs(roots[0][0])
    	q_ = abs(roots[1][0])
    	return (min(p_, q_), max(p_, q_))

    N = 
    phi = 
    f1 = (N + 1) - phi - p - q
    f2 = N - p*q
    p, q = solve(f1, f2)
    (p, q)

    参考：

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

    结式

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    from sage.matrix.matrix2 import Matrix
    def resultant(f1, f2, var):
        return Matrix.determinant(f1.sylvester_matrix(f2, var))

    n = 
    P.<k,t2,t3,d> = PolynomialRing(Integers(n))
    f1 = s1*k - h - r*d
    f2 = s2*(k+t2) - h - r*d
    f3 = s3*(k+t3) - h - r*d
    h1 = resultant(f1, f2, d)
    h2 = resultant(f1, f3, d)
    g1 = resultant(h1, h2, k)

    ​

  • WolframAlpha

    https://www.wolframalpha.com/