『CTF』从两道题目看 RSA 算法 – 作者:宸极实验室Sec-安全小百科

日期：2021-05-06

作者：Jgk01

介绍：早年两道RSA题目，考古发现比较有意思，大家感兴趣的可以先不看解题思路自己做一下，比较友好。

0x00 前言

RSA在平常比赛会经常遇到，之前在某平台遇到过一到适合理解基础RSA的题目，虽然不是很难，但是确实需要你对RSA密码熟悉，所以用来总结一下。

0x01 RSA算法介绍

1.1 RSA简介

RSA是被研究得最广泛的公钥算法，从提出到现在已近三十年，经历了各种攻击的考验，逐渐为人们接受，普遍认为是目前最优秀的公钥方案之一。RSA的具体加密解密流程如下：

1.2 RSA算法的具体描述

(1)任意选取两个不同的大素数p和q计算乘积:

(2)任意选取一个大整数e，满足:

(3)确定的解密钥d，满足 :

(4)公开整数k和e，秘密保存d；

(5)将明文m（m<n是一个整数）加密成密文c，加密算法为:

(6)将密文c解密为明文m，解密算法为:

(7)根据n和e要计算出d是不可能的。因此，任何人都可对明文进行加密，但只有授权用户（知道d）才可对密文解密。

0x02 第一道题目

2.1题目

n=24585768801100871989460458412563674690545986652089097718040761783186739174559136657307807040444318337561194142282186006216583089898423180103199568738639814413601595196467099996734334212909157604318709957690532885862891927163713619932622153281344607898846228206181834468325246573910857887714824338949742479585089251882243488454602710292507668577598274622372304293403731722318890268908300308478539449464617438721833942643889296634768118375076052778833640986893990732882252524850152650060780854621796349622086656401914022236044924841914313726991826438982902866584892213702893596657746111940812657202364588469026832387629
p-q=
14048479366496281701869293063643750801596179514889914988732592464154208813942939793532694949932787548745769133200541469022315588864587160064703369956054828780928008235304461825448872454098086255531582368864754318040219023548966787642948010656526691472780392631956031751285174567712974691729142190835749586660
e = 65537
c = 13043206753625359891696429504613068427529111016070088678736297291041435652992434742862062899975037273524389833567258051170507686131853178642412748377655159798601888072877427570380109085131089494464136940524560062629558966202744902709909907514127527274581612606840291391818050072220256661680141666883565331886278443012064173917218991474525642412407692187407537171479651983318468186723172013439034765279464665108704671733067907815695414348312753594497823099115037082352616886076617491904991917443093071262488786475411319592529466108485884029307606114810451140886975584959872328937471166255190940884805476899976523580343

2.2 解题思路

(1) 给了n，p-q，e，然后n很大，无法使用工具分解，感觉肯定是利用p-q这个点求d了。

(2) 那么这里就用到了一些关于初中数学的小知识，d=(p-1)(q-1)=pq-(p+q)+1
现在n=pq已经知道了，在求出来p+q就行了。呢么如何求p+q呢？

(3) 这里肯定要放眼到p-q的，首先(p-q)(p-q)=p*p+q*q-2n然后(p+q)(p+q)=p*p+q*q+2n,也就是说能求出来y=p+q

(4) 所以我们先求p+q：

import math
import gmpy2
n=24585768801100871989460458412563674690545986652089097718040761783186739174559136657307807040444318337561194142282186006216583089898423180103199568738639814413601595196467099996734334212909157604318709957690532885862891927163713619932622153281344607898846228206181834468325246573910857887714824338949742479585089251882243488454602710292507668577598274622372304293403731722318890268908300308478539449464617438721833942643889296634768118375076052778833640986893990732882252524850152650060780854621796349622086656401914022236044924841914313726991826438982902866584892213702893596657746111940812657202364588469026832387629
x=14048479366496281701869293063643750801596179514889914988732592464154208813942939793532694949932787548745769133200541469022315588864587160064703369956054828780928008235304461825448872454098086255531582368864754318040219023548966787642948010656526691472780392631956031751285174567712974691729142190835749586660
y=x*x
z=y+4*n
q=gmpy2.isqrt(z)
print q

(5)得到p+q以后这个剩下的步骤就是基础RSA求解明文代码如下：

#!/usr/bin/python
#coding:utf-8
import libnum
from Crypto.Util.number import long_to_bytes
x = 24585768801100871989460458412563674690545986652089097718040761783186739174559136657307807040444318337561194142282186006216583089898423180103199568738639814413601595196467099996734334212909157604318709957690532885862891927163713619932622153281344607898846228206181834468325246573910857887714824338949742479585089251882243488454602710292507668577598274622372304293403731722318890268908300308478539449464617438721833942643889296634768118375076052778833640986893990732882252524850152650060780854621796349622086656401914022236044924841914313726991826438982902866584892213702893596657746111940812657202364588469026832387629
y = 313911508194450175570632595955672449806614397067433716077861356318241639602539415146427164747918893278353408869473491895193527215277755282703791989765796626512243061215408359221962662362641939950515512881269464358321542098202690113744333540601483874730634934587010409040497502224033520896973739974013262725454
c = 13043206753625359891696429504613068427529111016070088678736297291041435652992434742862062899975037273524389833567258051170507686131853178642412748377655159798601888072877427570380109085131089494464136940524560062629558966202744902709909907514127527274581612606840291391818050072220256661680141666883565331886278443012064173917218991474525642412407692187407537171479651983318468186723172013439034765279464665108704671733067907815695414348312753594497823099115037082352616886076617491904991917443093071262488786475411319592529466108485884029307606114810451140886975584959872328937471166255190940884805476899976523580343
e = 65537
n = x
phi = n-y+1
d = libnum.invmod(e,phi)
m = pow(c,d,n)
print long_to_bytes(m)

这样就的到最后的flag了，这道题目虽然不是很难但是需要明白RSA中加密所需要的公钥对和私钥对到底是怎么来的。

0x03 第二道题目

3.1 题目链接

链接: https://pan.baidu.com/s/1j_0XeVRIxgflUfCc7o_bGw  密码: kq51

3.2 解题思路

(1) 首先题目给的很充足了，加密脚本还有加密后的得到的文件，n，e，c都写进去了。那么我们先来看加密脚本。

from Crypto.Util.number import bytes_to_long, getPrime
from random import randint
from gmpy2 import powmod
p = getPrime(2048)
q = getPrime(2048)
N = p*q
Phi = (p-1)*(q-1)
def get_enc_key(N,Phi):
    e = getPrime(N)
    if Phi % e == 0:
        return get_enc_key(N, Phi)
    else:
        return e
e1 = get_enc_key(randint(10, 12), Phi)
e2 = get_enc_key(randint(10, 12), Phi)
fr = open(r"./base64", "rb")#flag is in this file
f1 = open(r"./HUB1", "wb")
f2 = open(r"./HUB2", "wb")
base64 = fr.read(255)
f1.write("%d\n%d\n" % (N, e1))
f2.write("%d\n%d\n" % (N, e2))
while len(base64)>0:
    pt = bytes_to_long(base64)
    ct1 = powmod(pt, e1, N)
    ct2 = powmod(pt, e2, N)
    f1.write("\n%d" % ct1)
    f2.write("\n%d" % ct2)
    base64 = fr.read(255)
fr.close()
f1.close()
f2.close()

(2) 从代码中我们能知道这个加密代码从未给出的文件中读取了明文，经过加密输出了n，e，c。一个n两个e，两个密文，然后e1与e2互质，所以这里是共模攻击。

(3) 但是这里有个小坑：

base64 = fr.read(255)

他的c是255位一组来做的，所以不能把所有的c一股脑的解码，需要一段一段的解码。

(4) 解题脚本：

#!/usr/bin/python
 #coding:utf-8
import re
import gmpy2
from Crypto.Util.number import long_to_bytes
import base64

e1 = 1697
e2 = 599
n = 785095419718268286866508214304816985447077293766819398728046411166917810820484759314291028976498223661229395009474063173705162627037610993539617751905443039278227583504604808251931083818909467613277587874545761074364427549966555519371913859875313577282243053150056274667798049694695703660313532933165449312949725581708965417273055582216295994587600975970124811496270080896977076946000102701030260990598181466447208054713391526313700681341093922240317428173599031624125155188216489476825606191521182034969120343287691181300399683515414809262700457525876691808180257730351707673660380698973884642306898810000633684878715402823143549139850732982897459698089649561190746850698130299458080255582312696873149210028240898137822888492559957665067936573356367589784593119016624072433872744537432005911668494455733330689385141214653091888017782049043434862620306783436169856564175929871100669913438980899219579329897753233450934770193915434791427728636586218049874617231705308003720066269312729135764175698611068808404054125581540114956463603240222497919384691718744014002554201602395969312999994159599536026359879060218056496345745457493919771337601177449899066579857630036350871090452649830775029695488575574985078428560054253180863725364147
c1=36869806815936046911848195817405817350259890871483063184373728397968909458432625046025376290214729914038387534731762237978339011724858818860181178811639468996206294711495853807311240013786226884265118119546377272154555615363105236192878292703331473547623021744317034819416624562896226194523639793573028006666236271812390759036235867495803255905843636447252225413871038762657801345647584493917576263471587347202664391908570140389126903204602391093990827188675090199750617303773574821926387194478875191828814971296674530519321530805302667925998711835019806761133078403281404889374663875077339168901297819436499920958268483684335998301056068380228873524800383911402490807139268964095165069610454677558808756444381542173782815227920906224931028457073652453777424387873533280455944646592996920617956675786286711447540353883400282402551158169958389450168079568459656526911857835375748015814860506707921852997096156275804955989964215077733621769938075413007804223217091604613132253046399456747595300404564172224333936405545921819654435437072133387523533568472443532200069133022979195685683508297337961701169394794966256415112246587706103819620428258245999539040721929317130088874161577093962579487428358736401687123174207198251449851429295
c2=271453634732502613378948161256470991260052778799128789839624515809143527363206813219580098196957510291648493698144497567392065251244844074992734669490296293997386198359280316655904691639367482203210051809125904410431506925238374843856343243276508280641059690938930957474434518308646618959004216831130099873532714372402117796666560677624822509159287675432413016478948594640872091688482149004426363946048517480052906306290126242866034249478040406351940088231081456109195799442996799641647167552689564613346415247906852055588498305665928450828756152103096629274760601528737639415361467941349982213641454967962723875032638267311935042334584913897338553953961877439389588793074211502597238465542889335363559052368180212013206172712561221352833891640659020253527584706465205486408990762759230842192028381048563437724528409174790022752557512795782713125166158329880702730769957185428522011430144840232256419113631679343171680631630775266488738173707357123139368825087043785842169049943237537188129367275730984789479909103397937113837824575137021012333461552176687570010445744268373840742899299977372834041925102853718964831225250407279578465008537542659673685686242773379131904890865110699190451534445434533919127658976874721029586168106207
_, r, s = gmpy2.gcdext(e1, e2)
m = pow(c1, r, n) * pow(c2, s, n) % n
print long_to_bytes(m)

(5) 然后根据题目提示我们可以知道解出来base64是base64隐写，所以把这解出来的base64放到一个txt中然后利用base64隐写来解就行了。

# -*- coding: cp936 -*-
b64chars = 'ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/'
with open('tmp.txt', 'rb') as f:
    bin_str = ''
    for line in f.readlines():
      stegb64 = ''.join(line.split())
      rowb64 =  ''.join(stegb64.decode('base64').encode('base64').split())
      offset = abs(b64chars.index(stegb64.replace('=','')[-1])-b64chars.index(rowb64.replace('=','')[-1]))
      equalnum = stegb64.count('=') #no equalnum no offset
      if equalnum:
        bin_str += bin(offset)[2:].zfill(equalnum * 2)
    print ''.join([chr(int(bin_str[i:i + 8], 2)) for i in xrange(0, len(bin_str), 8)])

(6)这道题目结合了RSA的共模攻击与base64隐写，在比赛中结合考察多种知识点的情况也是很常见的。