CTF--RSA

RSA

理论基础

1、q、p 是两个大质数。

2、 N=p×q。

3、根据欧拉函数，求得 φ(N)=φ(p)φ(q)=(p−1)(q−1)。

4、选择一个小于 φ(N)的整数 e，使 e 和 φ(N)互质。

5、通过线性同余方程来求解 d，所谓求解线性同余方程，即求 x 的值。线性同余方程有解的条件是 a 与 b 的最大公约数可以被 c 整除。 x 称为 a mod b 的逆元。

在 rsa 中，e d ≡ 1 ( mod φ(N))，即求解 d，前提是 e 与 φ(N)的最大公约数能被 c 整除。求 d，即求 e mod φ(N)的逆元。

6、数据加解密

加密公式

m^ e ≡ c( mod N ) 等价于 c = m^e mod n

解密公式

c^d ≡ m ( mod N ) 等价于 m = c^d mon n

例如:

5 ≡ 2 mod 3 等价于 2 = 5 mod 3

因此在 python 中求明文为 pow(c,d,n)，求密文为 pow(m,e,n)。

7、公钥 e 用来加密，私钥 d 用来解密。

RSA 解题条件

1、e 小于 φ(N)。

2、e 和 φ(N)互质。

3、q、p 必须为质数。

4、能够计算出 d 的前提是线性同余方程 ax ≡ 1 ( mod b)有解，而有解的前提是 a 与 b 的最大公约数能被 c 整除，c=1，即 a 与 b 的最大公约数为 1，即使 e 与 φ(N)的最大公约数为 1，即 gcd(e,φ(N)==1。

数论基础

质数或素数

没有其他约数的数为素数，例如 1，2, 3，5，7。

互质

即互质是公约数只有 1 的两个整数，叫做互质整数。

欧拉函数

在 RSA 中需要根据欧拉函数求出 φ(N)的值。

φ(7) = 7-1 =6

即 1、2、3、4、5、6 与 7 互为质数。

1、

2、3、

倍数

10 能够被 5 整出，5 为 10 的约数，10 为 5 的倍数。

10 和 8 的公倍数为 80、40、400 等。

10 和 8 的最小公倍数为 40。

约数(因数)

10 能够被 5 整出，5 为 10 的约数，10 为 5 的倍数。

10 和 8 的公约数为 1、2、4。

最大公约数，也称最大公因数、最大公因子，指两个或多个整数共有约数中最大的一个。

例如:

a = 12, b = 8

其中 a 的约数为{1,2,3,4,6,12}，b 的约数为{1,2,4,8}，公约数为{1,2,4}，最大公约数为 4。

from gmpy2 import gcda = 12b = 8print(gcd(12,8))

如果两个数的最大公因数为 1，则两个数字互为素数。

from gmpy2 import gcda = 11b = 17print(gcd(a,b))

如果 a 和 b 都为素数，则 a 和 b 互为素数，如果 a 为素数，b<a，则 b 和 b 互为素数。

逆元

逆元是指使 ax≡1 (mod b)成立的 x 值，等价于 ax % b = 1。

欧几里得算法

欧几里德算法又称辗转相除法，用于计算两个整数 a,b 的最大公约数。即求 gcd(a,b)的值。

扩展欧几里得算法

拓展欧几里得算法是指找到两个整数，使得

a * u + b * v = gcd(a,b)。

扩展欧几里得算法与求逆元

因为逆元是指使 ax≡1 (mod b)成立的 x 值，所以等价于 ax % b = 1，即(ax-1)/b = y，其中 y 为整数。

等价于 ax-by = 1，即 ax+(-b)y = 1，根据拓展欧几里得算法，即 a * x + (-b) * y = 1 = gcd(a,-b) = gcd(a,b)。

即可以通过拓展欧几里得算法求逆元，也就是求 rsa 中的 d。

拓展欧几里得算法求两个整数

#-*-coding:utf-8-*- # 扩展欧几里得算法# 输入m n # 输出 m n的最大公约数 还有s,t# # 默认 m > nimport sysdefexgcd(m,n,x,y):if n == 0:                x = 1                y = 0return (m,x,y)        a1 = b = 1        a = b1 = 0        c = m        d = n        q = int(c/d)        r = c%dwhile r:                c = d                d = r                t = a1                a1 = a                a = t-q*a                t = b1                b1 = b                b = t-q*b                q = int(c/d)                r = c%d        x = a        y = breturn (d,x,y)m = int(sys.argv[1])n = int(sys.argv[2])ans = exgcd(m,n,0,0)print("gcd(%d,%d) = %d"%(m,n,ans[0]))print("s = %d, t = %d"%(ans[1],ans[2]))

模运算

a ≡ b mod m，即 a mod m = b mod n，即 a ≡ b mod m <=> a % m = b

求解

11 ≡ x mod 68146798528947 ≡ y mod 17

for i in range(0,1000):if11 % 6 == i % 6:        print(i)for i in range(0,1000):if8146798528947 % 17 == i % 17:        print(i)

费马小定理

from gmpy2 import *print(pow(3,17,17))print(pow(4,17,17))print(pow(5,17,17))print(pow(6,17,17))print(pow(7,17,17))print("=================")print(pow(3,16,17))print(pow(4,16,17))print(pow(5,16,17))print(pow(6,16,17))print(pow(7,16,17))34567=================11111

求 p = 65537，计算 273246787654^65536 mod 65537，p 为素数，且 gcd(273246787654，65537)，那么 273246787654^65536 mod 65537 = 1。

p = 65537a = 273246787654if gcd(a,b) == 1:    print(1)

费马小定理与求逆元

3 * d ≡ 1 mod 13，求 d。

3 * d ≡ 1 mod 13 ==> d ≡ 3^-1 mod 13

print(pow(3, -1, 13))

3 * d ≡ 1 mod 13

a^(p-1)  ≡ 1 mod p

a^(p-1) = a*a^(p-2)

a*a^(p-2)  ≡ 1 mod p

3 * d ≡ 1 mod 13

a = 3

a^(p-2) = a^(13-2)

d = a^(13-2) mod 13

print(pow(3,11,13))

模方跟

r^2 ≡ a mod p

**from** **sage.rings.finite_rings.integer_mod** **import** square_root_mod_primeprint(square_root_mod_prime(Mod(a,p),p))

二次剩余

即 x^2-a 可以被 p 整除，x^2 ≡ a (mod p)等价于 a = x^2 mod p，因此此时 x^2 一定小于 29。

p = 29ints = [14, 6, 11]p为模数，ints中有二次剩余和二次非剩余，求出二次剩余并求出对应的平方根。

解法 1

p = 29x2 = [14, 6, 11]for x in x2:for i in range(0,29):if (i**2 -x) % p == 0:            print(i,x)

解法 2

p = 29x2 = [14, 6, 11]for a in range(29):if pow(a,2,p) in x2:        print(pow(a,2,p),a)

欧拉定理

如果两个正整数 a 和 n 互质，则 n 的欧拉函数 φ(n) 可以让下面的等式成立：

a^φ(N) = 1 (mod n)，也就是说，a 的 φ(n)次方被 n 除的余数为 1。或者说，a 的 φ(n)次方减去 1，可以被 n 整除。

余数

取余数运算 a mod b = c（b 不为 0）表示整数 a 除以整数 b 所得余数为 c。

同余

m^e ≡ c mod n，即 m^e mod n 的余数为 c。即 m^e mod n = c mod n = c。c<n。

同余性质

同余方程

求同余方程的解

使用 sage 进行求解

sage: **from** **Crypto.Util.number** **import** *....: n= **7**....: PR.<x> = PolynomialRing(Zmod(**7**))....: f = x^**5**+**2***x^**4**+x^**3**+**2***x^**2**-**2***x+**3**....: l=f.roots()....: **for** i in l:....:     print(i)

线性同余方程

线性同余方程是最基本的同余方程，即 ax ≡ b (mod n)。

中国剩余定理

即求满足以下条件的整数：除以 3 余 2，除以 5 余 3，除以 7 余 2。

求解如下形式的一元线性同余方程组，其中 n1、n2、n3、nk 两两互质）

Python 使用

获取质数

import sympyfrom gmpy2 import *np=842868045681390934539739959201847552284980179958879667933078453950968566151662147267006293571765463137270594151138695778986165111380428806545593588078365331313084230014618714412959584843421586674162688321942889369912392031882620994944241987153078156389470370195514285850736541078623854327959382156753458023print(sympy.nextprime(np))输出:842868045681390934539739959201847552284980179958879667933078453950968566151662147267006293571765463137270594151138695778986165111380428806545593588078365331313084230014618714412959584843421586674162688321942889369912392031882620994944241987153078156389470370195514285850736541078623854327959382156753458569

判断是否是质数

import gmpy2#判断一个数是否为素数a = gmpy2.is_prime(842868045681390934539739959201847552284980179958879667933078453950968566151662147267006293571765463137270594151138695778986165111380428806545593588078365331313084230014618714412959584843421586674162688321942889369912392031882620994944241987153078156389470370195514285850736541078623854327959382156753458023)c = gmpy2.is_prime(842868045681390934539739959201847552284980179958879667933078453950968566151662147267006293571765463137270594151138695778986165111380428806545593588078365331313084230014618714412959584843421586674162688321942889369912392031882620994944241987153078156389470370195514285850736541078623854327959382156753458569)print(a)print(c)输出:FalseTrue

数值开方

gmpy.iroot(a,b)

理解为 a 开 b 次方，这个函数的返回值为一个(x,y)元组，其中 x 为结果值，y 为一个 bool 型变量，如果 x 为整数，y=True,否则 y=False。

import gmpy2(a,b) = gmpy2.iroot(710426542430767315216760794114622199691609874204743190419177803336685631663181323322014423739860007487797965472505492560515520347998262609038656216986939090718874499676284246152337203150331278432328271624281993234848078997863629219265115870819791150259792580588801597844476348690113461466450979506426424549999508405668764321788561357788588409902382079078124970997888946423628535870045211475341990922624843345676616546475567376975265965235167219485525557619369272138253902135102109948308463357689863617500147889709178815410667610944325138911775808087960460960848259994197560449857590535712662528798363217559839440,2)print(a)或者(gmpy2.iroot(n1,2))[0]

判断两个数字是否互为质数

import gmpy2p=139916095583110895133596833227506693679306709873174024876891023355860781981175916446323044732913066880786918629089023499311703408489151181886568535621008644997971982182426706592551291084007983387911006261442519635405457077292515085160744169867410973960652081452455371451222265819051559818441257438021073941183q=842868045681390934539739959201847552284980179958879667933078453950968566151662147267006293571765463137270594151138695778986165111380428806545593588078365331313084230014618714412959584843421586674162688321942889369912392031882620994944241987153078156389470370195514285850736541078623854327959382156753458569phi = (p-1)*(q-1)a = gmpy2.gcd(phi,65537)print(a)输出:如果结果为1，则为互为质数。

逆元(D)

如果有 ed ≡ 1(mod φ(n))，则称 d 的最小正整数解为 a 模 φ(n)的逆元。

import gmpy2n=117930806043507374325982291823027285148807239117987369609583515353889814856088099671454394340816761242974462268435911765045576377767711593100416932019831889059333166946263184861287975722954992219766493089630810876984781113645362450398009234556085330943125568377741065242183073882558834603430862598066786475299918395341014877416901185392905676043795425126968745185649565106322336954427505104906770493155723995382318346714944184577894150229037758434597242564815299174950147754426950251419204917376517360505024549691723683358170823416757973059354784142601436519500811159036795034676360028928301979780528294114933347127c=75186169332770398011618387278278132278790899252552138882799075432380607926731546030253687400295924217369315868839672386616943227315064045460865365296683033483186291570240079759200380250862319608787524113935879604728967164231477966741805601564635364322718438051545168770427777047667842857584346659655292503627681225184738425341914431617445650748762586933275572200060984083928949491872172407901109108320296584642767891651443970128071209300594102046815811229697489154488296004024544579726109722995921635677648742873800015194793794148142345457719541079982444120634269256199324030425798299206933898605904024426172410823p=139916095583110895133596833227506693679306709873174024876891023355860781981175916446323044732913066880786918629089023499311703408489151181886568535621008644997971982182426706592551291084007983387911006261442519635405457077292515085160744169867410973960652081452455371451222265819051559818441257438021073941183q=842868045681390934539739959201847552284980179958879667933078453950968566151662147267006293571765463137270594151138695778986165111380428806545593588078365331313084230014618714412959584843421586674162688321942889369912392031882620994944241987153078156389470370195514285850736541078623854327959382156753458569phi = (p-1)*(q-1)a = gmpy2.invert(65537,(p-1)*(q-1))print(a)输出:8599589881775512182490339390302384847126810744233969198532121090013876515514061191844004921719994842305490870513682688025890863319222633068753414378485078624510630709922513396281417153363777832648184544232199294766471900485392788050293515601012127448268872412182805907996901141107293140818104160339368182321217372234809523842344722549604286239338414176997138752498663184064331483582259621245748238876057665171100280468834141443144340932719393320666917904802256624401993129580989389345716562456345455121702090606106185465724822179950100180548721991615891176882567105125169912160252167465495939533501038099782250065

解密

m  ≡  c^d mod n

pow(c, d, n)

加密

c ≡   m^e mod n

c=pow(m,e,n)

flag 转化

from Crypto.Util.number import *print(long_to_bytes(1920535408007397834236393374892057067669865609963495845501))print(bytes_to_long(b'NSSCTF{why_gongmo_again}'))

出题脚本

随机质数

from Crypto.Util.number import *print(getPrime(1024))

求平方

print(pow(2,3))

左移和右移

右移动运算符，把 >> 左边的运算数的各二进制位全部右移若干位，>> 右边的数字指定了移动的位数。

左移动运算符，运算数的各二进制位全部左移若干位，而 << 右边的数字指定了移动的位数，高位丢弃，低位补 0。

from Crypto.Util.number import long_to_bytes,bytes_to_long,getPrimep=getPrime(512)print("p={}".format(p))print("p右移200位:{}".format(p>>200))p=Integer(p>>200)print("p右移之后的位数为:{}".format(p.nbits()))p=Integer(p<<200)print("p右移动200位，在左移之后的位数为:{}".format(p.nbits()))

获取位数

sage: n = **91268904297188837924801498062177690165796176137884686076382364249045888382423376832621725398436742313748794322102233305695129031641032488978**....: **46564587898621**....: print(n.nbits())

密文的处理方式

from Crypto.Util.number import long_to_bytes,bytes_to_long,getPrimeimport libnumm="13290194973860029392268109531737773490765214878528074799765092464208146798025846271931332989"print(long_to_bytes(int(m)))print(libnum.n2s(int(m)))

Sage 的使用

同余方程

ax^2+bx+c=0(mod p)

solve_mod([a*x^**2**+b*x+c==**0**], **54787**)[(39866,), (49785,)]

求 phi

n = 21711308225346315542706844618441565741046498277716979943478360598053144971379956916575370343448988601905854572029635846626259487297950305231661109855854947494209135205589258643517961521594924368498672064293208230802441077390193682958095111922082677813175804775628884377724377647428385841831277059274172982280545237765559969228707506857561215268491024097063920337721783673060530181637161577401589126558556182546896783307370517275046522704047385786111489447064794210010802761708615907245523492585896286374996088089317826162798278528296206977900274431829829206103227171839270887476436899494428371323874689055690729986771phi = euler_phi(n)

方程

from Crypto.Util.number import bytes_to_long, getPrimefrom gmpy2 import *from flag import flagm = bytes_to_long(flag)p = getPrime(2048)q = getPrime(2048)n = p * qe = 65537gift = 2022 * p + 9 * q + 28 * ec = pow(m,e,n)print(n,c,gift)# 559013759419746202691240598235115105126834606071307611491891982898293133657843987454339580258031532272691584368719342942404675509580909313170933925796189789232538297110756754383546447669571766593521267667716779348776308179675709803388978100416839504625045239819627379469827980589668625084314985969634985583431058156810528172627873121320455715399011186280324236548934145366222271636328254497851289112650375015433741699898290781472376090171361276557886637892800404830030548291487615566596504234212554381817510798554015481259307992175226543595948798873846335558746933940683482819439715578130806800536423771482474206047548549237879025655562739463111822524633757040958223066367993671472508367287181357997804485542311011003871312708995599690715923692968372474814753669031805664070760705148563294700043336457334028810890271434599241312612447640877347296648737167576464851763570272180801042067934843953206083053874624644994067168364645748243999074053494066054657595233970985982095621265309066132852511490426399921749091156312387594448586826952283581592003247165562367202134878625798756167825941929996806801073247649667626854029875184014003650020610359836971629737204456239324237077361643697429780638179887750984791035339697744210904151734797# 73407318923483936681380982096598838839602514018601041044571793373013418096970487001956204920233481604663088115926046001478564679328045899017826536373925483312496867862798918521256833686293905627264784839084309695013473729502056597198558911052248943918139429481528120149662544426266704140382476129564563832751550189116712164319522536680400998100426969878312141399338984622535922004572374724499994480294086487511972287034778386491943792466926044305651852709046949243652756946391206931252732067537917128777152678266816232179411054474713462051435447023851233892017069674808619784767176865947753180156093197684363218543237706358137237603822953178987601908200096630034921280599733190041134038060644827637374731999991143342404380959195318030935855850625849684867326087432054830971960076859722417639414733054394674533018860606074648324450983897579183842853010968597034663149214229791831193351337193195298921766564073265470525286769595835642479920483047959570057149110246705969802722576770273329236163660486942433423522588321736639231667766680582482974393228214947178327111783901303686854030864244720750585928819691608599558058859371899416709995780300197269497143959726959313506292966639680257096421491364629690813416340577056873916752193925# 63829120016023768052886024054478552450378183173692549289836790500844466624984770449526584263524969873611417764466777251459739549064993441916734929304056657281688756040121378172997367361118927461471925755841160032723693319039128805185488328610549652307644061769088611063117016010827595409949224043526660999362737741312450095192593608666286680915796697255817583078927076945852260612453896867746751729217633935143780193497702898684210698859292191506586139420497299988065973759272644964857853100511651254633164029275099534568064491202987945733565755982565356202756330311841048849063747767451397616638500281324618902190280761

解方程

n,p,q=var("n p q")solve([p*q==306354583002946747992937563543921375708985311385263456197789027033121717576398311343108209462848269036771397662201427300496561337677898886678093122384687917410559402035311025351919618951520629739488546705557099436801994269958198693525149946896571699486034234820299571303825153222907093868174385895403009413647013113509062243571839874367055539398876851646824314126042247237309773075977903217506249870718381497556804600313073903477293635927085073739615959842101027871007903123323505375609878797900680469180874394443933831334375308912803199865044862330323853230225150817191101645018610108743909108994950186620980337059015721532561929536996212788979853487908596470347555913171358856115616441973434823833800448313860771567452755970427426178169231314611984109045507876643873020864196777458683121606741969345964919696405052801023790667895317356961559020419026343273126491564852987965069415070412461875910678767188232927597492997899623110660407388797282715754550035052111332115990055108450820197539551715931171320258043343210114697339003307322612847958692128271240172001826061075308478525062551559972727458828334449974765110506067332842301966014015418352309586629840013845570225084578398507980641852586841359791057995696511950560393395255637,2022*p+9*q+28*65537==36914399239611593971816978851156951312599320020772372368458829970400963749631692062023214005813876443040577989185916291359812639909058106421410717056973385411512229248115930123060214170029934933709029442080446656715357969090363988646326109072727275570940704850479219890522576258356334743040342882085788851899435015399001901125639499110190368490364023346890242329887292065373936530432545845533937845385082915725014475153398400425217614779431562471480988276376600143229970740615907558777346812592563363965086617075420502954894890226572947870535045717601859934506954162485834056049126070245761794482095183827910913598029911],n,p,q)# b'NSSCTF{S4g3_is_4_g00d_thing}'