[关闭]
@bintou 2017-10-31T14:28:08.000000Z 字数 4594 阅读 933

Crypto-related Codes in Sage

Code Crypto Sage


RSA Code

Basis Algorithm

  1. #https://www.math.ucdavis.edu/~anne/FQ2010/Number_Theory_RSA.html
  2. def rsa_kg(bits):
  3. # only prove correctness up to 1024 bits
  4. proof = (bits <= 1024)
  5. p = next_prime(ZZ.random_element(2**(bits//2+1)), proof=proof)
  6. q = next_prime(ZZ.random_element(2**(bits//2+1)), proof=proof)
  7. n = p*q
  8. phi_n = (p-1)*(q-1)
  9. while True:
  10. e = ZZ.random_element(1,phi_n)
  11. if gcd(e,phi_n) == 1: break
  12. d = lift(Mod(e,phi_n)^(-1))
  13. return e, d, n
  14. def encrypt(m, e, n):
  15. return lift(Mod(m,n)^e)
  16. def decrypt(c, d, n):
  17. return lift(Mod(c,n)^d)
  18. def encode(s):
  19. s = str(s)
  20. return sum(ord(s[i])*256^i for i in range(len(s)))
  21. def decode(n):
  22. n = Integer(n)
  23. v = []
  24. while n != 0:
  25. v.append(chr(n % 256))
  26. n //= 256 # this replaces n by floor(n/256)
  27. return ''.join(v)
  28. e,d,n = rsa_kg(1024)
  29. m = encode('Meet me at 4.'); m
  30. c = encrypt(m,e,n); c
  31. M = decrypt(c,d,n); M
  32. decode(M)

Common Modulus Attack

Given e, d, N and e1, compute d1 such that d1 is a valid decrypting exponent for the public key (e1 , N )

  1. k1 = gcd(e1 , e*d 1)
  2. k2 = (e*d 1) / k1
  3. d1 = xgcd(e1, k2) [1]

Small d attack

攻击成功的条件:q < p < 2q and that d < n^{1/4}/3

0、生成弱秘钥

  1. def rsa_weak_kg(bits):
  2. # only prove correctness up to 1024 bits
  3. proof = (bits <= 1024)
  4. p = next_prime(ZZ.random_element(2**(bits//2+1)), proof=proof)
  5. q = next_prime(ZZ.random_element(2**(bits//2+1)), proof=proof)
  6. n = p*q
  7. phi_n = (p-1)*(q-1)
  8. while True:
  9. d = ZZ.random_element(2**(bits//4))
  10. if gcd(d,phi_n) == 1 and 36*pow(d, 4) < n: break
  11. e = lift(Mod(d,phi_n)^(-1))
  12. return e, d, n

1、算e/n的连分数

  1. fra = (e/n).continued_fraction()

2、依次选择fra对e/N的逼近,记为k/d,利用这个k和d进行N的分解

  1. # Define f(x)= (x - p)(x - q) = 0
  2. # x = var('x')
  3. # a , b, c = 1, 1, 1
  4. # qe = (a*x^2 + b*x + c == 0)
  5. # Trials
  6. def small_d_attack(fra):
  7. for i in range(1, len(fra)):
  8. k = fra.numerator(i)
  9. d = fra.denominator(i)
  10. if k != 0:
  11. phi = (d*e - 1)/k
  12. a = 1
  13. b = -(n - phi + 1)
  14. c = n
  15. # Define f(x)= (x - p)(x - q) = 0
  16. x = var('x')
  17. qe = (a*x^2 + b*x + c == 0)
  18. sol = solve(qe, x)
  19. p = sol[0].right()
  20. q = sol[1].right()
  21. if p.is_integer() and q.is_integer() and q*p == n:
  22. print sol[0].right(), sol[1].right()
  23. print "We found the decrypting exponent.", d
  24. break

Discrete Logarithm

Sage下Dlog的求解命令

  1. F.<a>=GF(2^16+1)
  2. g=F.multiplicative_generator()
  3. u=g**12345
  4. discrete_log(u,g)
  5. # discrete_log_rho(u,g) can't work for composite order group.

DLOG实例生成

  1. # p is a prime and q is (p-1)/2 and also a prime. Thus Zq* is a subgroup of Zp* with prime order.
  2. def dlog_gen(n):
  3. p = next_prime(n)
  4. while not is_prime( floor((p-1)/2) ):
  5. p = next_prime(p)
  6. x = randint(1,p-1)
  7. y = randint(1,p-1)
  8. g = x*x % p
  9. h = y*y % p
  10. return [p,floor( (p-1)/2 ),g,h]

Baby-Step Giant-Step DLOG

  1. # Generate a random DLOG instance.
  2. def dlog_gen(bits):
  3. p = next_prime(ZZ.random_element(2**bits))
  4. q = floor((p-1)/2)
  5. while not is_prime(q):
  6. p = next_prime(p)
  7. q = floor((p-1)/2)
  8. g = 1
  9. while g == 1:
  10. x = randint(1, p-1)
  11. g = x*x % p
  12. return [p,q,g]
  13. # Baby Step Giant Step DLP problem a = g**x mod n
  14. # Input: g,a,n where g is the generator, a = g^x mod n,
  15. def dlog_bgs(a, g, n):
  16. s = floor(sqrt(n))
  17. A = []
  18. B = []
  19. for r in range(0,s):
  20. value = a*(g^r) % n
  21. A.append(value)
  22. for t in range(1,s+1):
  23. value = g^(t*s) % n
  24. B.append(value)
  25. #print A
  26. #print B
  27. x1,x2 =0,0
  28. for u in A:
  29. for v in B:
  30. if u == v:
  31. x1 = A.index(u)
  32. x2 = B.index(v)
  33. #print x1,x2
  34. break
  35. #print 'the value of x is ', ((x2+1)*s - x1) % n # Answer
  36. return ((x2+1)*s - x1) % n

Pollard rho discrete logarithm

  1. # A simple Pollard rho discrete logarithm
  2. # implementation and has some limitations:
  3. # 1. p must be a prime that equals 2q + 1
  4. # 2. q must be a prime, too
  5. # 3. g generates a sub group with order q
  6. # 4. a belongs to <g>, the subgroup generated by g
  7. # these four limitations made this program simpler
  8. # x = log_g(a) in Zp
  9. # assert: classify(1) != 1
  10. def classify(x):
  11. # 3n + 2 -> S0
  12. # 3n -> S1
  13. # 3n + 1 -> S2
  14. return (x + 1) % 3
  15. def succssor(x, s, t, p, q, g, a):
  16. c = classify(x)
  17. if c == 0:
  18. return (g * x) % p, (s + 1) % q, t
  19. elif c == 1:
  20. return (x * x) % p, (2 * s) % q, (2 * t) % q
  21. else: # c == 2
  22. return (a * x) % p, s, (t + 1) % q
  23. def dlog_rho(a, g, p, q):
  24. xa, sa, ta = 1, 0, 0
  25. xb, sb, tb = succssor(1, 0, 0, p, q, g, a)
  26. while xa != xb:
  27. xa, sa, ta = succssor(xa, sa, ta, p, q, g, a)
  28. xb, sb, tb = succssor(xb, sb, tb, p, q, g, a)
  29. xb, sb, tb = succssor(xb, sb, tb, p, q, g, a)
  30. s, t = sa - sb, tb - ta
  31. if s == 0:
  32. return 'fail'
  33. if s < 0:
  34. s = s + q
  35. if t < 0:
  36. t = t + q
  37. res = xgcd(t, q)[1]
  38. if res < 0 :
  39. res = res + q
  40. res = (res * s) % q
  41. return res
  42. # How to use in Sage and compare with discrete_log and discrete_log_rho
  43. bits = 30
  44. p,q,g = dlog_gen(30)
  45. x = 120
  46. a = Mod(g,p)^x
  47. time discrete_log(a, g, p)
  48. time discrete_log_rho(a, g, q)
  49. #dlog_bgs(g, a, p)
  50. #dlog_rho(g, a, p, q)

WStein 2017 Elementary Number Theory

Chapter 6 ECC

  1. #Code from WStein 2017 Elementary Number Theory
  2. from sage.libs.libecm import ecmfactor
  3. ecmfactor(2^128+1,1000,sigma=227140902)
  4. # Pollard p-1 method
  5. def pollard(N, B=10^5, stop=10):
  6. m = prod([p^int(math.log(B)/math.log(p)) for p in prime_range(B+1)])
  7. for a in [2..stop]:
  8. x = (Mod(a,N)^m - 1).lift()
  9. if x == 0: continue
  10. g = gcd(x, N)
  11. if g!=1 or g != N: return g
  12. return 1
  13. # Lenstra's EC method
  14. def ecm(N, B=10^3, trials=10):
  15. m = prod([p^int(math.log(B)/math.log(p)) for p in prime_range(B+1)])
  16. R = Integers(N)
  17. # Make Sage think that R is a field:
  18. R.is_field = lambda : True
  19. for _ in range(trials):
  20. while True:
  21. a = R.random_element()
  22. if gcd(4*a.lift()^3 + 27, N) == 1: break
  23. try:
  24. m * EllipticCurve([a, 1])([0,1])
  25. except ZeroDivisionError, msg:
  26. # msg: "Inverse of <int> does not exist"
  27. return gcd(Integer(str(msg).split()[2]), N)
  28. return 1
  29. #set_random_seed(2)
  30. #ecm(5959, B=20)
  31. #ecm(next_prime(10^20)*next_prime(10^7), B=10^3)
添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注