EN | ZH

RSA 介绍

RSA 加密算法是一种非对称加密算法。在公开密钥加密和电子商业中 RSA 被广泛使用。RSA 是 1977 年由罗纳德·李维斯特(Ron Rivest)、阿迪·萨莫尔(Adi Shamir)和伦纳德·阿德曼(Leonard Adleman)一起提出的。RSA 就是他们三人姓氏开头字母拼在一起组成的。

RSA 算法的可靠性由极大整数因数分解的难度决定。换言之,对一极大整数做因数分解愈困难,RSA 算法愈可靠。假如有人找到一种快速因数分解的算法的话,那么用 RSA 加密的信息的可靠性就肯定会极度下降。但找到这样的算法的可能性是非常小的。如今,只有短的 RSA 密钥才可能被强力方式解破。到 2017 年为止,还没有任何可靠的攻击 RSA 算法的方式。

基本原理

公钥与私钥的产生

  1. 随机选择两个不同大质数 pq,计算 N = p \times q
  2. 根据欧拉函数,求得 \varphi (N)=\varphi (p)\varphi (q)=(p-1)(q-1)
  3. 选择一个小于 \varphi (N) 的整数 e,使 e\varphi (N) 互质。并求得 e 关于 \varphi (N) 的模反元素,命名为 d,有 $ed\equiv 1 \pmod {\varphi (N)} $
  4. p​q​ 的记录销毁

此时,(N,e) 是公钥,(N,d) 是私钥。

消息加密

首先需要将消息 以一个双方约定好的格式转化为一个小于 N,且与 N 互质的整数 m。如果消息太长,可以将消息分为几段,这也就是我们所说的块加密,后对于每一部分利用如下公式加密:

m^{e}\equiv c\pmod N

消息解密

利用密钥 d​ 进行解密。

c^{d}\equiv m\pmod N

正确性证明

即我们要证m^{ed} \equiv m \bmod N,已知ed \equiv 1 \bmod \phi(N),那么 ed=k\phi(N)+1,即需要证明

m^{k\phi(N)+1} \equiv m \bmod N

这里我们分两种情况证明

第一种情况 gcd(m,N)=1​,那么 m^{\phi(N)} \equiv 1 \bmod N​,因此原式成立。

第二种情况 gcd(m,N)!=1,那么 m 必然是 p 或者 q 的倍数,并且 n=m 小于 N。我们假设

m=xp

那么 x 必然小于 q,又由于 q 是素数。那么

m^{\phi(q)} \equiv 1 \bmod q

进而

m^{k\phi(N)}=m^{k(p-1)(q-1)}=(m^{\phi(q)})^{k(p-1)} \equiv 1 \bmod q

那么

m^{k\phi(N)+1}=m+uqm

进而

m^{k\phi(N)+1}=m+uqxp=m+uxN

所以原式成立。

基本工具

RSAtool

  • 安装

    git clone https://github.com/ius/rsatool.git
    cd rsatool
    python rsatool.py -h
    
  • 生成私钥

    python rsatool.py -f PEM -o private.pem -p 1234567 -q 7654321
    

RSA Converter

  • 根据给定密钥对,生成 pem 文件
  • 根据 n,e,d 得出 p,q

openssl

  • 查看公钥文件

    openssl rsa -pubin -in pubkey.pem -text -modulus
    
  • 解密

    rsautl -decrypt -inkey private.pem -in flag.enc -out flag
    

更加具体的细节请参考 openssl --help

分解整数工具

python 库

primefac

整数分解库,包含了很多整数分解的算法。

gmpy

  • gmpy.root(a, b),返回一个元组 (x, y),其中 xab 次方的值,y 是判断 x 是否为整数的布尔型变量

gmpy2

安装时,可能会需要自己另行安装 mfpr 与 mpc 库。

  • gmpy2.iroot(a, b),类似于 gmpy.root(a,b)

pycrypto

  • 安装

    sudo pip install pycrypto
    
  • 使用

    import gmpy
    from Crypto.Util.number import *
    from Crypto.PublicKey import RSA
    from Crypto.Cipher import PKCS1_v1_5
    
    msg = 'crypto here'
    p = getPrime(128)
    q = getPrime(128)
    n = p*q
    e = getPrime(64)
    pubkey = RSA.construct((long(n), long(e)))
    privatekey = RSA.construct((long(n), long(e), long(d), long(p), long(q)))
    key = PKCS1_v1_5.new(pubkey)
    enc = key.encrypt(msg).encode('base64')
    key = PKCS1_v1_5.new(privatekey)
    msg = key.decrypt(enc.decode('base64'), e)
    

Jarvis OJ - Basic - veryeasyRSA

p = 3487583947589437589237958723892346254777 q = 8767867843568934765983476584376578389

e = 65537

求 d =

请提交 PCTF{d}

直接根据 $ed\equiv 1 \pmod{\varphi (N)} $,其中 \varphi (N)=\varphi (p)\varphi (q)=(p-1)(q-1),可得 d。

import gmpy2
p = 3487583947589437589237958723892346254777
q = 8767867843568934765983476584376578389
e = 65537
phin = (p - 1) * (q - 1)
print gmpy2.invert(e, phin)
➜  Jarvis OJ-Basic-veryeasyRSA git:(master) ✗ python exp.py       
19178568796155560423675975774142829153827883709027717723363077606260717434369

2018 CodeGate CTF Rsababy

程序就是一个简单的 RSA,不过程序还生成了两个奇怪的数

e = 65537
n = p * q
pi_n = (p-1)*(q-1)
d = mulinv(e, pi_n)
h = (d+p)^(d-p)
g = d*(p-0xdeadbeef)

所以,问题应该出自这里,所以我们就从此下手,不放这里先假设 const = 0xdeadbeef。那么

eg = ed*(p-const)

进而,根据 RSA 可知

2^{eg}=2^{ed*(p-const)}=2^{p-const} \pmod n
2^{p-const}*2^{const-1} = 2^{p-1} \pmod n

所以

2^{p-1} = 2^{eg}*2^{const-1}+kn

而与此同时根据费马小定理,我们知道

2^{p-1} \equiv 1 \pmod p

所以

p|2^{p-1}-1 | 2^{eg+const-1}-1+kn

进而

p|2^{eg+const-1}-1

所以

p|gcd(2^{eg+const-1}-1,n)

因此,代码如下

tmp = gmpy2.powmod(2,e*g+const-1,n)-1
p = gmpy2.gcd(tmp,n)
q = n/p
phin = (p-1)*(q-1)
d =gmpy2.invert(e,phin)
plain = gmpy2.powmod(data,d,n)
print hex(plain)[2:].decode('hex')

2018 国家安全周 pure math

题目的基本描述是这个样子的

1) p ** p % q = 1137973316343089029387365135250835133803975869258714714790597743585251681751361684698632609164883988455302237641489036138661596754239799122081528662395492
2) q ** q % p = 6901383184477756324584651464895743132603115552606852729050186289748558760692261058141015199261946483809004373728135568483701274908717004197776113227815323
3) (p ** q + q ** p) % (p*q) = 16791287391494893024031688699360885996180880807427715700800644759680986120242383930558410147341340225420991368114858791447699399702390358184412301644459406
4) (p+q) ** (p+q) % (p*q) = 63112211860889153729003401381621068190906433969243079543438386686621389392583849748240273643614258173423474299387234175508649197780206757067354426424570586101908571600743792328163163458500138799976944702155779196849585083397395750018148652864158388247163109077215394538930498877175474225571393901460434679279
5) FLAG ** 31337 % (p*q) = 6931243291746179589612148118911670244427928875888377273917973305632621316868302667641610838193899081089153471883271406133321321416064760200919958612671379845738048938060512995550639898688604592620908415248701721672948126507753670027043162669545932921683579001870526727737212722417683610956855529996310258030
Now, what’s the FLAG???

我们的目的基本上就是求得 Flag,那么怎么做呢?这个题目需要我们具有较好的数论功底。

根据题目中这样的内容,我们可以假设 p,q 都是大素数,那么

p^{q-1} \equiv 1\bmod q

那么

p^{q} \equiv p \bmod pq

那么我们可以根据 3 知道

p^q+q^p \equiv p+q \bmod pq

而 p+q 又显然小于 pq,所以我们就知道 p+q 的数值。

进一步,我们假设1,2,3,4,5对应的值分别为x1~x5则

根据4,我们可以知道

(p+q)^{p+q} \equiv p^{p+q}+q^{p+q} \bmod pq

又因为 1 和 2,则

p^pp \equiv px_1\bmod pq

q^qq \equiv qx_2 \bmod pq

因此

px_1+qx_2 \equiv x_4 \bmod pq

根据 x1 和 x2 的求得方式,我们可以知道这里也是等号,因此我们得到了一个二元一次方程组,直接求解即可。

import gmpy2
x1 = 1137973316343089029387365135250835133803975869258714714790597743585251681751361684698632609164883988455302237641489036138661596754239799122081528662395492
x2 = 6901383184477756324584651464895743132603115552606852729050186289748558760692261058141015199261946483809004373728135568483701274908717004197776113227815323
p_q = 16791287391494893024031688699360885996180880807427715700800644759680986120242383930558410147341340225420991368114858791447699399702390358184412301644459406
x4 = 63112211860889153729003401381621068190906433969243079543438386686621389392583849748240273643614258173423474299387234175508649197780206757067354426424570586101908571600743792328163163458500138799976944702155779196849585083397395750018148652864158388247163109077215394538930498877175474225571393901460434679279

if (x4 - x1 * p_q) % (x2 - x1) == 0:
    print 'True'
q = (x4 - x1 * p_q) / (x2 - x1)
print q
p = p_q - q

c = 6931243291746179589612148118911670244427928875888377273917973305632621316868302667641610838193899081089153471883271406133321321416064760200919958612671379845738048938060512995550639898688604592620908415248701721672948126507753670027043162669545932921683579001870526727737212722417683610956855529996310258030

phin = (p - 1) * (q - 1)
d = gmpy2.invert(31337, phin)
flag = gmpy2.powmod(c, d, p * q)
flag = hex(flag)[2:]
print flag.decode('hex')

flag 如下

2018-国家安全周第一场-puremath git:(master) ✗ python exp.py
True
7635093784603905632817000902311635311970645531806863592697496927519352405158721310359124595712780726701027634372170535318453656286180828724079479352052417
flag{6a66b8d5-6047-4299-a48e-4c4d1f874d12}

2018 Pwnhub LHY

首先分析这段代码

assert gmpy.is_prime(y)**2016 + gmpy.is_prime(x + 1)**2017 + (
    (x**2 - 1)**2 % (2 * x * y - 1) + 2
)**2018 == 30097557298197417800049182668952226601954645169633891463401117760245367082644152355564014438095421962150109895432272944128252155287648477680131934943095113263121691874508742328500559321036238322775864636883202538152031804102118831278605474474352011895348919417742923873371980983336517409056008233804190890418285814476821890492630167665485823056526646050928460488168341721716361299816947722947465808004305806687049198633489997459201469227952552870291934919760829984421958853221330987033580524592596407485826446284220272614663464267135596497185086055090126893989371261962903295313304735911034185619611156742146

由于 gmpy.is_prime 要么返回1,要么返回 0,所以我们可以很容易地试出来 y 是素数,x+1 也是素数,并且

(x^2-1)^2\equiv 0 \bmod (2xy-1)

为了式子能够整除,猜测 x=2y

于是,对于下面的内容

p = gmpy.next_prime(x**3 + y**3)
q = gmpy.next_prime(x**2 * y + y**2 * x)
n = p * q
phi = (p - 1) * (q - 1)
d = gmpy.invert(0x10001, phi)
enc = pow(bytes_to_long(flag), 0x10001, n)
print 'n =', n
print 'enc =', enc

p 和 q 自然为

p=nextp(9y^3)

q=nextp(6y^3)

根据素数的间隔,可以知道 p 和 q 最多比括号里的数字大一点,这里一般不会超过1000。

那么

n \geq 54y^6

所以我们知道了 y 的上界,而对于 y 的下界其实也不会离上界太远,我们大概减个几十万。进而,我们利用二分查找的方式来寻找 p 和 q,如下

import gmpy2
tmp = 30097557298197417800049182668952226601954645169633891463401117760245367082644152355564014438095421962150109895432272944128252155287648477680131934943095113263121691874508742328500559321036238322775864636883202538152031804102118831278605474474352011895348919417742923873371980983336517409056008233804190890418285814476821890492630167665485823056526646050928460488168341721716361299816947722947465808004305806687049198633489997459201469227952552870291934919760829984421958853221330987033580524592596407485826446284220272614663464267135596497185086055090126893989371261962903295313304735911034185619611156742146

print gmpy2.iroot(tmp, 2018)
print gmpy2.iroot(tmp - 1, 2018)

print gmpy2.iroot(tmp - 2, 2018)

n = 260272753019642842691231717156206014402348296256668058656902033827190888150939144319270903947159599144884859205368557385941127216969379550487700198771513118894125094678559478972591331182960004648132846372455712958337042783083099376871113795475285658106058675217077803768944674144803250791799957440111855021945690877200606577646234107957498370758707097662736662439460472126493593605957225541979181422479704018055731221681621886820626215670393536343427267329350730257979042198593215747542270975288047196483958369426727778580292311145109908665004662296440533724591193527886702374790526322791818523938910660223971454070731594803459613066617828657725704376475527288174777197739360634209448477565044519733575375490101670974499385760735451471034271880800081246883157088501597655371430353965493264345172541221268942926210055390568364981514774743693528424196241142665685211916330254113610598390909248626686397970038848966187547231199741

y = 191904757378974300059526915134037747982760255307942501070454569331878491189601823952845623286161325306079772871025816081849039036850918375408172174102720702781463514549851887084613000000L
y = gmpy2.next_prime(y)

enc = 73933313646416156737449236838459526871566017180178176765840447023088664788672323530940171469589918772272559607026808711216932468486201094786991159096267208480969757088208089800600731106685561375522764783335332964711981392251568543122418192877756299395774738176188452197889668610818741062203831272066261677731889616150485770623945568369493256759711422067551058418926344060504112146971937651406886327429318390247733970549845424064244469193626197360072341969574784310397213033860597822010667926563087858301337091484951760613299203587677078666096526093414014637559237148644939541419075479462431789925219269815364529507771308181435591670281081465439913711912925412078002618729159141400730636976744132429329651487292506365655834202469178066850282850374067239317928012461993443785247524500680257923687511378073703423047348824611101206633407452837948194591695712958510124436821151767823443033286425729473563002691262316964646014201612

end = gmpy2.iroot(n / 54, 6)[0]
beg = end - 2000000

mid = 1
while beg < end:
    mid = (beg + end) / 2
    if gmpy2.is_prime(mid) != 1:
        mid = gmpy2.next_prime(mid)
    p = gmpy2.next_prime(9 * mid**3)
    q = gmpy2.next_prime(6 * mid**3)
    n1 = p * q
    if n1 == n:
        print p, q
        phin = (p - 1) * (q - 1)
        d = gmpy2.invert(0x10001, phin)
        m = gmpy2.powmod(enc, d, n)
        print hex(m)[2:].strip('L').decode('hex')
        print 'ok'
        exit(0)
    elif n1 < n:
        beg = mid
    else:
        end = mid
    print beg, end

评论