技术分享 | 浅谈 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?}`

原文发布于微信公众号 - 安恒网络空间安全讲武堂(gh_fa1e45032807)

原文发表时间:2017-12-01

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏张善友的专栏

通过XML签名和加密更安全地交换数据

作者:Mike Downen、Shawn Farkas 相关技术:XML、.NET Framework、C#、安全性 [摘要]XML签名和XML加密标准目前被...

879100
来自专栏Linyb极客之路

spring系列之自定义扩展PropertyPlaceHolderConfigurer

一、PropertyPlaceHolderConfigurer介绍 主要用于将一些配置信息移出xml文件,移到至properties文件 二、拓展使用 1、将...

1.1K50
来自专栏我是攻城师

Java中4大基本加密算法解析

87950
来自专栏余林丰

利用Java提供的Observer接口和Observable类实现观察者模式

对于观察者模式,其实Java已经为我们提供了已有的接口和类。对于订阅者(Subscribe,观察者)Java为我们提供了一个接口,JDK源码如下: 1 pack...

25580
来自专栏Android机动车

RxJava从入门到不离不弃(一)——基本概念和使用

RxJava的编程思想已经在Android开发者中变得越来越流行。有个不好的点就是上手不太容易,尤其是大部分人之前都是使用命令式编程语言。

10220
来自专栏zcqshine's blog

SpringMVC下获取验证码

52280
来自专栏Fundebug

JWT究竟是什么呢?

为了保证可读性,本文采用意译而非直译。另外,本文版权归原作者所有,翻译仅用于学习。

13170
来自专栏xingoo, 一个梦想做发明家的程序员

【手把手教你全文检索】Apache Lucene初探

PS: 苦学一周全文检索,由原来的搜索小白,到初次涉猎,感觉每门技术都博大精深,其中精髓亦是不可一日而语。那小博猪就简单介绍一下这一周的学习历程,仅供各位程...

278100
来自专栏我的博客

PHP开发微信公共平台(验证token)ZendFramework

define('TOKEN', '3FC50DEAED1083F162BB3D36FF053709'); //这个是TOKEN,...

37340
来自专栏小鄧子的技术博客专栏

All RxJava - 为Retrofit添加重试

在我们的日常开发中离不开I/O操作,尤其是网络请求,但并不是所有的请求都是可信赖的,因此我们必须为APP添加请求重试功能。

36610

扫码关注云+社区

领取腾讯云代金券