RSA攻击

参加个CTF比赛，发现自己零代码量，什么东西都没有准备，被吊打当然正常，基本的工具常用的代码可以自己提前写好的呀

常用的代码有：

gcd：求两个数的最大公约数

egcd：求满足ax+by=1，当gcd（a，b）=1时，满足式子的x和y

hextoflag：很多题目都是给的字母的ord值：两位两位表示一个字母，转化成chr字符就是flag的

b64：base64解密

b32：base32解密

qp：quickpow，快速幂运算

modinv：求cd=1（mod m），在已知c，m，且gcd（c，m）=1的时候，求得c的逆元d

get_phi_n：求n的欧拉函数（这个是做RSA题专用的分解n，因为n是两个大素数相乘）

attacksamen：RSA公模攻击

原理：

http://www.math1as.com/index.php/archives/360/?utm_source=tuicool&utm_medium=referral

http://bobao.360.cn/learning/detail/3058.html

modequation：求ax=b（mod c）的x，一次同余方程，有解的条件是，b % gcd（a，c）=0

代码如下：

#!/usr/bin/env python
# coding=utf-8

from pwn import *
from gmpy2 import iroot
import hashlib
import base64  
import sys
from Crypto.Util.number import bytes_to_long, long_to_bytes
import gmpy2
sys.setrecursionlimit(10000000)  

def hextonumber(x):
	#1234567890abcdef
	#1234567890ABCDEF
	if x>='0' and x<='9':
		return int(x)
	elif x>='A' and x<='F':
		return ord(x)-55
	else:
		return ord(x)-87

def hextoflag(s):
	#word='666c61677b7769656e65725f61747461636b5f61747461636b5f796f757d'
	#flag{wiener_attack_attack_you}
	flag = ''
	i = 0
	while (i<len(s)):
		flag += chr(hextonumber(s[i])*16+hextonumber(s[i+1]))
		i += 2
	return flag

def b64(s):
	#word = 'Y3RmezY2NjY2Nn0='
	#ctf{666666}
	return base64.b64decode(s)

def b32(s):
	#word = 'GYYWIY3UMZ5UQML6IIYHSLCXMVWEGMDNMUWVI3ZNJAZVEZL5'
	#61dctf{H1~B0y,WelC0me-To-H3Re}
	return base64.b32decode(s)

def gcd(a, b):
   if a < b:
     a, b = b, a
   while b != 0:
     temp = a % b
     a = b
     b = temp
   return a

def egcd(a,b):
    if b==0:
        return a,1,0
    else:
        g,x,y=egcd(b,a%b)
        return g,y,x-a/b*y

def qp(n,m,p):
    ans=1
    while(m):
        if (m%2==1):
            ans=(ans*n)%p
        n=(n*n)%p
        m=m/2
    return ans

def egcd(a, b):
    if a == 0:
        return (b, 0, 1)
    else:
        g, y, x = egcd(b % a, a)
        return (g, x - (b // a) * y, y)

def modinv(a, m):
    g, x, y = egcd(a, m)
    if g != 1:
        raise Exception('modular inverse does not exist')
    else:
        return (x+m) % m

def get_phi_n(p,q):
    return (p-1)*(q-1)

def attacksamen(n,e1,e2,c1,c2):
	s = egcd(e1 , e2)
	s1 = s[1]
	s2 = s[2]
	if s1 < 0:
		s1 = - s1
		c1 = modinv (c1 , n)
	elif s2 < 0:
		s2 = - s2
		c2 = modinv (c2 , n)
	m = ( qp(c1,s1,n) * qp(c2,s2,n) ) % n
	return hextoflag(str(hex(m))[2:-1])

def modequation(a,b,c):
	#ax==b(mod c)
	#ax+cy==b
	#b%gcd(a,c)==0
	Gcd = gcd(a,c)
	if (b % Gcd != 0):
		return 'No Solution'
	a /= Gcd
	c /= Gcd
	b /= Gcd
	return b*modinv(a,c)%c

if __name__ == "__main__":
	#hextoflag = 
	#b64 = base64.b64decode
	#b32 = base32.b32decode
	#gcd = greatest common divisor
	#egcd =
	#qp = (n^m)%p
	#modinv = (e*d)==1 % n , we have number e and number n to get number d
	#get_phi_n(p,q)
	#attacksamen
	#n = 0x18f60afa6b9938df69338805ae7fbd5652da3ac8fa5b7b65e4755149ba3f80d071fe8845fa20ea3e57e21fb2f630e47e4886de35c51d1487c170a59141f833c3aaea62c539e20664dbfa75f1b2d56ed4dbec991e5bf3306931bfda79b1dd8466f808af159b44be042499d423110ab9cfd595e370029862e2e686ed2a27fb6b459c4fddc0ebd4f112e0f3769524412e7128eb04b02de421df5a0e5b22d2c40acf1727aa9093160bf6dbd862ac136a805a4e9c760c54d28ac5bf21d509d94e9e437e2e38a13664ec104dadc66f8c21b7b82e3e3570d27326e13df07dd72b6847f8e53aadeafa54cc879cfa2ae3b8028c39df36b097ba65688abadb78a06c16f393L
	#e1 = 0x17e1
	#e2 = 0x43a5
	#c1 = 0xb6e66aa0d4d5ad1460482f45aab87e80a99c1ff3af605fd9cea82d76d464272f3dd2e1797e3fede64cffcd54b2a7a5e21f45574783f62266cebf3cdb9764c6c04b0b30b5d065d5f6142d498506ea1f6449f428253d4d76bd96778d5f58abf313370b980dcb90daf882c5539ac3df81a431bc2c0e0911ecbe5195d94312218b3854ee14f13bd00c81d7ff11c06a9e112940b7377c20e53738a2ebb77b0534d8d9e481e60e9c87693bd9e1fd1e569083479ff8f53e42337a2b799c2325a7e2588fb046cf228d01d8596e7af4570a3cb0635d2524d234e3993d76b7e60f1c478ba45891de5cc0a1fec116f7c0dd9be7aa54226edf0196e37856afca32c69d790e1L
	#c2 = 0x9bcbfea3c3130364bbcf352b7810df031293949ed147919dec3ecfdd48f77e9486ae811d95f8c79eb477f4424d475dc611536343c7e21c427e18593aae37982323f2c0f4e840fbf89b31edc8f79ad7f6511ee0e5605cfbba7ada7d8777e81ec0ac122e0ad5108e97fafc0cd31ed8c83f3e761b92bdbea1144b0c06c5ca43a7b4e9e0a2b15ee12509235c5695be54d9fd0725ac80abbf0f5e8f43539da3ce9464020099e031d8bca899f11638169196ac72aeaeb90dab851d801cf93044cc00dd94d93c8963201b26788a7c42ce45c496c0a597ac53cd55c60b8f38f3f7d1f8ecc2e4e40ba6fe0c6e605ebbfc9aa3da5ab810c783c1d9957bb5d00a89ab1bbdeL
	#print attacksamen(n,e1,e2,c1,c2)
	#print modequation(5,4,12)
	#print modequation(15,11,36)
	letter = 'abcdefghijklmnopqrstuvwxyz'
	word = 'falszztysyjzyjkywjrztyjztyynaryjkyswarztyegyyj'
	flag = ''
	for i in word:
		flag += letter[modequation(7,(ord(i)-97+4)%26,26)]
	print flag