RSA-已知ed分解n

• 基本操作

  1. 取$k=ed-1$
  2. 在$(2, n-1)$随机选择g，令$t=k$
  3. 如果t能被2整除，令$t=t/2，x=g^t\ mod\ n$，否则回到第二步
  4. 如果x-1与n不互质，那么$p=gcd(x-1,n)，q = n/p$，否则回到第三步

  d泄露后，仅更换e是白给的，必须选择一个新的n

• 证明

  俺自己瞎证的

  $k=ed-1$，k为偶数，可写为$k=2^sr$，r为奇数，s>1

  由欧拉定理，若g，n互质，则$g^{φ(n)}\ ≡ 1\ mod\ n$，所以

  $g^{ed-1}\ ≡ 1\ mod\ n$

  $a_0=g^r,a_1=(a_0)^2,…,a_s=(a_{s-1})^2，a_s\ ≡ 1\ mod\ n$

  若$x^2≡ 1\ mod\ n$，即$(x+1)(x-1)≡ 0\ mod\ n$，且$x≠1，x≠n-1$，则$gcd(x-1,N)>0$

  所以若$a_i<n，a_{i+1}\ ≡ 1\ mod\ n，x=a_imodn=a_i$，可以得到n的一个因数$x-1$

• Python实现

  import random
  import gmpy2
  def divide_pq(e, d, n):
      k = e*d - 1
      while True:
          g = random.randint(2, n-1)
          t = k
          while True:
              if t % 2 != 0:
                  break
              t /= 2
              x = pow(g, t, n)
              if x > 1 and gmpy2.gcd(x-1, n) > 1:
                  p = gmpy2.gcd(x-1, n)
                  return (p, n/p)   
  

• HCTF2016 Crypto So Interesting

  题目

  #! /usr/bin/env python
  # -*- coding: utf-8 -*-
    
  from flag import get_flag
  from hashlib import sha512
  from Crypto.Util.number import getPrime,bytes_to_long
  from libnum import invmod, gcd
  import random
    
  __author__ = 'Hcamael'
    
  def m_exit(n):
  	print "==============Game Over!================="
  	exit(n)
    
  def cal_bit(num):
  	num = int(num)
  	l = len(bin(num))
  	return l-2
    
  def pi_b(x):
  	bt = 536380958350616057242691418634880594502192106332317228051967064327642091297687630174183636288378234177476435270519631690543765125295554448698898712393467267006465045949611180821007306678935181142803069337672948471202242891010188677287454504933695082327796243976863378333980923047411230913909715527759877351702062345876337256220760223926254773346698839492268265110546383782370744599490250832085044856878026833181982756791595730336514399767134613980006467147592898197961789187070786602534602178082726728869941829230655559180178594489856595304902790182697751195581218334712892008282605180395912026326384913562290014629187579128041030500771670510157597682826798117937852656884106597180126028398398087318119586692935386069677459788971114075941533740462978961436933215446347246886948166247617422293043364968298176007659058279518552847235689217185712791081965260495815179909242072310545078116020998113413517429654328367707069941427368374644442366092232916196726067387582032505389946398237261580350780769275427857010543262176468343294217258086275244086292475394366278211528621216522312552812343261375050388129743012932727654986046774759567950981007877856194574274373776538888953502272879816420369255752871177234736347325263320696917012616273L
  	return invmod(x, bt)
    
  def get_ed(p, q):
  	k = cal_bit(q*p)
  	phi_n = (p-1)*(q-1)
  	r = random.randint(10, 99)
  	while True:
  		u = getPrime(k/4 - r)
  		if gcd(u, phi_n) != 1:
  			continue
  		t = invmod(u, phi_n)
  		e = pi_b(t)
  		if gcd(e, phi_n) == 1:
  			break
  	d = invmod(e, phi_n)
  	return (e, d)
    
  def verify():
  	print "Proof of Work"
  	with open("/dev/urandom") as f:
  		prefix = f.read(5)
  	print "Prefix: %s" %prefix.encode('base64')
  	try:
  		suffix = raw_input()
  		s = suffix.decode('base64')
  	except:
  		m_exit(-1)
  	r = sha512(prefix + s).hexdigest()
  	if "fffffff" not in r:
  		m_exit(-1)
    
  def main():
  	verify()
  	print "This is a RSA Decryption System"
  	print "Please enter Your team token: "
  	token = raw_input()
  	try:
  		flag = get_flag(token)
  		assert len(flag) == 38
  	except:
  		print "Token error!"
  		m_exit(-1)
    		
  	p=getPrime(2048)
  	q=getPrime(2048)
  	n = p * q
  	e, d = get_ed(p, q)
  	print "n: ", hex(n)
  	print "e: ", hex(e)
    
  	flag = bytes_to_long(flag)
  	enc_flag = pow(flag, e, n)
  	print "Your flag is: ", hex(enc_flag)
    	
    
  if __name__ == '__main__':
  	main()
  

  bt = 536380958350616057242691418634880594502192106332317228051967064327642091297687630174183636288378234177476435270519631690543765125295554448698898712393467267006465045949611180821007306678935181142803069337672948471202242891010188677287454504933695082327796243976863378333980923047411230913909715527759877351702062345876337256220760223926254773346698839492268265110546383782370744599490250832085044856878026833181982756791595730336514399767134613980006467147592898197961789187070786602534602178082726728869941829230655559180178594489856595304902790182697751195581218334712892008282605180395912026326384913562290014629187579128041030500771670510157597682826798117937852656884106597180126028398398087318119586692935386069677459788971114075941533740462978961436933215446347246886948166247617422293043364968298176007659058279518552847235689217185712791081965260495815179909242072310545078116020998113413517429654328367707069941427368374644442366092232916196726067387582032505389946398237261580350780769275427857010543262176468343294217258086275244086292475394366278211528621216522312552812343261375050388129743012932727654986046774759567950981007877856194574274373776538888953502272879816420369255752871177234736347325263320696917012616273
  u = getPrime(k/4 - r)
  t = invmod(u, phi_n)
  e = invmod(t, bt)
  

  可以算出t，t=invmod(e, bt)

  t为u对φ(n)的模反元素，u的位数为k/4 - r，满足 Wiener’s Attack 条件，可以求出t

  $ut ≡ 1\ mod\ n$，已知u，t，n，可以分解n得到pq

  t = invert(e,bt)
  u = wiener_attack(t,n)
  p,q = divide_pq(u*t,N)
  phin = (p-1)*(q-1)
  d = invert(e,phin)
  c =
  p = pow(c,d,n)