技术分享 | 浅谈 RAS
技术分享 | 浅谈 RAS
一 首先介绍一下什么是RSA
RSA算法是一种非对称密码算法，所谓非对称，就是指该算法需要一对密钥，使用其中一个加密，则需要用另一个才能解密。
RSA的算法涉及三个参数，n、e1、e2。
其中，n是两个大质数p、q的积，n的二进制表示时所占用的位数，就是所谓的密钥长度。
e1和e2是一对相关的值，e1可以任意取，但要求e1与(p-1)*(q-1)互质；再选择e2，要求(e2×e1)≡1(mod(p-1)×(q-1))。
（n，e1),(n，e2)就是密钥对。其中(n，e1)为公钥，(n，e2)为私钥。
RSA加解密的算法完全相同，设A为明文，B为密文，则：A≡B^e2( mod n)；B≡A^e1 (mod n)；（公钥加密体制中，一般用公钥加密，私钥解密）
e1和e2可以互换使用，即：
A≡B^e1 (mod n)；B≡A^e2( mod n);
二
再介绍一下常见的RSA工具
1.RSATool
这个工具相当直接
其中：
Keysize(Bits)：填写你N的位数
Public Exp.(E)：填写你的e的十进制值
Number Base：填写你下面N的进制（一般采用10进制）
Modulus(N)：填写N的十进制数（和Number Base填写的要对应）
- 然后点击左下角的Factor N
- 就会自动分解出P和Q
- 然后点击左下角的Calc. D
- 就会自动计算出D
- 然后点击左下角的Test（这里好像有个Bug，要先加密一次，才能用解密功能）
- 然后把你的密文放在result里，点击decrypto，即可得到解密后的答案
2.yafu
一个相当方便的大数分解工具
使用指令：（到yafu-x64.exe的目录下使用）
yafu-x64.exe factor(N)
例如要把大数87924348264132406875276140514499937145050893665602592992418171647042491658461分解
只需要：
yafu-x64.exe factor(87924348264132406875276140514499937145050893665602592992418171647042491658461)
即可
3.PARI
这个我工具我用的比较少了，一般是用来将大数16进制转10进制……或者是判断N的位数使用
指令也很简单：
第一步:x=87924348264132406875276140514499937145050893665602592992418171647042491658461
（当然，如果输入16进制，你要带上0x，他会底下自动给你显示10进制，十分方便）
第二步:binary(x)
他就会帮你把这个大数分解成2进制
第三步:length(x)
他可以帮你输出这个N的位数
4.openssl
经常会遇到类似如下格式的公钥:
-----BEGIN PUBLIC KEY-----
MIGfMA0GCSqGSIb3DQEBAQUAA4GNADCBiQKBgQCh5Nk2GLiyQFMIU+h3OEA4UeFb
u3dCH5sjd/sLTxxvwjXq7JLqJbt2rCIdzpAXOi4jL+FRGQnHaxUlHUBZsojnCcHv
hrz2knV6rXNogt0emL7f7ZMRo8IsQGV8mlKIC9xLnlOQQdRNUssmrROrCG99wpTR
RNZjOmLvkcoXdeuaCQIDAQAB
-----END PUBLIC KEY-----
可以使用RSA将其转换成N和E的形式，指令如下:
openssl rsa -in public.key -pubin -noout -text -modulus
即可得到N和E
三
分析一道RSA经典题目
（来自上海赛DCTF的一道RSA）
题目程序
#!/usr/bin/python
from hashlib import md5
from Crypto.Util.number import getPrime,bytes_to_long,long_to_bytes
from libnum import invmod
from os import urandom
import random
import sys
def auth():
global secret
print "Give me your username"
sys.stdout.flush()
username = raw_input()
username = username.rstrip("\n")
print "Give me your token"
sys.stdout.flush()
token = raw_input()
token = token.rstrip("\n")
if md5(secret+username).hexdigest() != token:
print "Token error!"
sys.stdout.flush()
return 0
elif username.find("root")>=0:
return 1
else:
print "Permission deny!"
sys.stdout.flush()
return 0
def welcome():
global secret
#secret="hahahaha"
md5obj=md5()
md5obj.update(secret+"guest")
token=md5obj.hexdigest()
print "Welcome to RRRSA world!"
print "This is your token:",token
sys.stdout.flush()
def regen_key():
global phi_n,e,d
print "e =",e
print "d =",d
print "The value above will be abondanded!"
sys.stdout.flush()
e = getPrime(16)
d = invmod(e, phi_n)
def read_flag():
f=open("./flag")
return f.readline()
f.close()
def print_flag_enc():
global e,n,d
flag = read_flag()
flag_long=bytes_to_long(flag)
flag_enc=pow(flag_long,e,n)
print "flag_enc =",flag_enc
def read_int():
try:
x = raw_input()
x = int(x)
return x
except ValueError:
return -1
def option():
print "There are some options for you!"
print "1. regenerated the key"
print "2. get public key"
print "3. get encrypted flag"
print "Option:"
sys.stdout.flush()
return read_int()
len_n=2048
secret=urandom(8)
p = getPrime(len_n/2)
q = getPrime(len_n/2)
n = p * q
phi_n = (p-1) * (q-1)
e = getPrime(16)
d = invmod(e, phi_n)
welcome()
for i in range(3):
op=option()
if op==1:
if auth():
regen_key()
elif op==2:
print "n =",n
print "e =",e
sys.stdout.flush()
elif op==3:
print_flag_enc()
sys.stdout.flush()
break
else:
print "Wrong Option"
sys.stdout.flush()程序分析
一共3个选项:
print "1. regenerated the key"
print "2. get public key"
print "3. get encrypted flag"
选项1:
def auth():
global secret
print "Give me your username"
sys.stdout.flush()
username = raw_input()
username = username.rstrip("\n")
print "Give me your token"
sys.stdout.flush()
token = raw_input()
token = token.rstrip("\n")
if md5(secret+username).hexdigest() != token:
print "Token error!"
sys.stdout.flush()
return 0
elif username.find("root")>=0:
return 1
else:
print "Permission deny!"
sys.stdout.flush()
return 0
def regen_key():
global phi_n,e,d
print "e =",e
print "d =",d
print "The value above will be abondanded!"
sys.stdout.flush()
e = getPrime(16)
d = invmod(e, phi_n)容易想到这里应该是一个hash长度拓展攻击
因为secret是我们已知长度，不知具体的salt
而secret+username我们已知知道了secret+guest的md5
所以我们可以利用hashpump进行攻击，从而成为root，得到第一组e和d
然后选项2：
print "n =",n
print "e =",e
可以给出重新生成的n和e
然后选项3：
def print_flag_enc():
global e,n,d
flag = read_flag()
flag_long=bytes_to_long(flag)
flag_enc=pow(flag_long,e,n)
print "flag_enc =",flag_enc可以给出第二轮生成的e和n得到的密文
程序攻击
首先我们确定一下思路:
先得到第一轮的e和d，再得到第二轮重新生成的e和不变的n，最后获取flag
所以我们首先进行hash长度拓展攻击
这里我们选择pwntools与题目进行交互
from pwn import *
from hashpumpy import *
p=remote('106.75.98.74
',10030)
p.recvuntil('This is your token: ')
h=p.recvline().strip()
a=hashpump(h,'guest','root',8)
p.recv()
p.sendline('1')
p.recv()
p.sendline(a[1])
p.recv()
p.sendline(a[0])
print p.recv()
p.interactive()
可以容易得到第一组e和d
e = 40213
d = 7500700469928887286518458227664699159278535487520757641922238090199917409016343569173939993906922756556831035504721854231002147097871069085579605909683755970246918670465100763853106096318395019569333288936689100858056883923422787373585911487853097453104638315266112565971841143733065838415785677352565366518286696159642641689659349714647415916777285391063620441166105432812587414551700794114394465506916507947677896007952395030521123001124229725209405882460927276297059921329305310826295983712199378473680414182815794064434492991619912020752957362646533601970102561949600259252301371098109684898098632567518246029061然后获取不变的n和第二轮的e：
n = 16524717470949999696091971769521752440260107793769365422375442958484045294952841940896929215744211078147145479140490874058581566934021218492215673721914911457379024844979625103644603925450699551960861203528794105780148001600427357073029653134336087650342235280326312639863345637042556103665917352949033642897308785366329872282202458250082221058049458136595784478449079400726888282283678741404349251932226122657413860087195339718695834408124378779278152097697039166079786373183546878203429827668279703612664272707566842472777033850849491863616969677973480717909379202648999260739897757062596992962034283964483339890331
e = 51713最后是密文:
c=14393216781722178003306512831950927649138730534659938473432658453893579089181643910227146230219873790364049290575161577576737668749258349821047730143664996540304846267849691627722700417655460486917490004775172766040499375305064669817859170100795609015892650599502208001994020595343601282023820768649108270834062429381494838401660862935250942907635115481123369593205062636738018108000462370324278749923060060752122371413390939737682554633793909003693581999343058203409653003990465873405008587925422815425152341277900009601352181012736488572123959271273718435444053362323902987467288142530197426611139316340183388954578然后问题来了，如果用已知的n,e,d去得到p和q
这里我一开始思考了一下：
我们可以知道
d = e^-1 mod phi_n
所以我们容易得到
d*e = 1 mod phi_n
即
d*e-1|phi_n
所以我们可以分解`d*e-1`，他必有因素是phi_n，得到phi_n后我们就可以得到第二轮的d
但是由于分解的因素过多，直接排列组合配对出phi_n就很痛苦
所以这里有一个很好的算法:
https://www.di-mgt.com.au/rsa_factorize_n.html
可以很好的帮我们解决问题
算法实现:
import random
def gcd(a, b):
if a < b:
a, b = b, a
while b != 0:
temp = a % b
a = b
b = temp
return a
def getpq(n, e, d):
p = 1
q = 1
while p == 1 and q == 1:
k = d * e - 1
g = random.randint(0, n)
while p == 1 and q == 1 and k % 2 == 0:
k /= 2
y = pow(g, k, n)
if y != 1 and gcd(y - 1, n) > 1:
p = gcd(y - 1, n)
q = n / p
return p, q
def main():
n = 16524717470949999696091971769521752440260107793769365422375442958484045294952841940896929215744211078147145479140490874058581566934021218492215673721914911457379024844979625103644603925450699551960861203528794105780148001600427357073029653134336087650342235280326312639863345637042556103665917352949033642897308785366329872282202458250082221058049458136595784478449079400726888282283678741404349251932226122657413860087195339718695834408124378779278152097697039166079786373183546878203429827668279703612664272707566842472777033850849491863616969677973480717909379202648999260739897757062596992962034283964483339890331
e = 40213
d = 7500700469928887286518458227664699159278535487520757641922238090199917409016343569173939993906922756556831035504721854231002147097871069085579605909683755970246918670465100763853106096318395019569333288936689100858056883923422787373585911487853097453104638315266112565971841143733065838415785677352565366518286696159642641689659349714647415916777285391063620441166105432812587414551700794114394465506916507947677896007952395030521123001124229725209405882460927276297059921329305310826295983712199378473680414182815794064434492991619912020752957362646533601970102561949600259252301371098109684898098632567518246029061
p, q = getpq(n, e, d)
print p
print q
if __name__ == '__main__':
main()可以得到p和q：
p = 116803972359246830950002720138413077148113956408220776890535345803005303891268315330897200540246172887169335591551592243064609663151911089959259139601097749649631698099961451191394321447353119887438164810634953619671204382075221416442255785950963637188549460847726333017672845807932145101586045638150628232999
q = 141473933952570870291987109677740142115118495048607431322824021521561294210766639642610839458071357533353534950484614107837113133499907017656928417943568186729082488790080005204231835973916579530731477122069042925690924156112706754053655741356596095895117019307476005281377103443987986040076775474329685986669
然后就很简单了，直接可以得到flag
n = 16524717470949999696091971769521752440260107793769365422375442958484045294952841940896929215744211078147145479140490874058581566934021218492215673721914911457379024844979625103644603925450699551960861203528794105780148001600427357073029653134336087650342235280326312639863345637042556103665917352949033642897308785366329872282202458250082221058049458136595784478449079400726888282283678741404349251932226122657413860087195339718695834408124378779278152097697039166079786373183546878203429827668279703612664272707566842472777033850849491863616969677973480717909379202648999260739897757062596992962034283964483339890331
c = 14393216781722178003306512831950927649138730534659938473432658453893579089181643910227146230219873790364049290575161577576737668749258349821047730143664996540304846267849691627722700417655460486917490004775172766040499375305064669817859170100795609015892650599502208001994020595343601282023820768649108270834062429381494838401660862935250942907635115481123369593205062636738018108000462370324278749923060060752122371413390939737682554633793909003693581999343058203409653003990465873405008587925422815425152341277900009601352181012736488572123959271273718435444053362323902987467288142530197426611139316340183388954578
e = 51713
p=141473933952570870291987109677740142115118495048607431322824021521561294210766639642610839458071357533353534950484614107837113133499907017656928417943568186729082488790080005204231835973916579530731477122069042925690924156112706754053655741356596095895117019307476005281377103443987986040076775474329685986669
q=116803972359246830950002720138413077148113956408220776890535345803005303891268315330897200540246172887169335591551592243064609663151911089959259139601097749649631698099961451191394321447353119887438164810634953619671204382075221416442255785950963637188549460847726333017672845807932145101586045638150628232999
d = modinv(e,(p-1)*(q-1))
m = fastExpMod(c,d,n)
print hex(m)
flag:`flag{Do_you_think_change_e_d_means_change_the_key?}`