CTF-CRYPTO-RSA-SupplementRabin

• SupplementRabin
• • 题目分析
  • 开始
  • • 1.题目
    • 2.分析
    • • （1）关系
      • （2）gift分解
      • （3）数学原理
      • （4）最大公因数范围
      • （5）e不是素数
    • 3.完整脚本
    • 4.get flag
  • 结语

有时间就多更新一两题

SupplementRabin

题目分析

1. supplement rabin
2. lcm最小公倍数

开始

1.题目

task.py

#!/usr/bin/env python
# -*- coding: utf-8 -*-
import gmpy2
from libnum import n2s,s2n
from Crypto.Util.number import getPrime

p = getPrime(1024)
q = getPrime(1024)
n = p * q
e = 62674

gift = gmpy2.lcm(p - 1 , q - 1)

flag = 'flag{******}'
m = s2n(flag)
c = pow(m, e, n)

print('n: ', n)
print('gift: ', gift)
print('c: ', c)

# n = 10955952193867109007049171223448361703270316163381595475808977909570592186241572786000524779399251175639632506214659739654167891613877009909733465445850342326411605633577886819119591988666107494251525119526649254044083570299541059529064752255209948208082218652104303247582539992747196312466088319880461301389139117606269407703870835019991154758699118376408730038824561166793173838184174470555371713764515850687815448410533112337309598350391951304786480700678337420633644297059882623208007530826126677786131600580363410319193803307063974046834458230446741602905632962163026760269893441525950972199909583357468982874081
# gift = 456498008077796208627048800977015070969596506807566478158707412898774674426732199416688532474968798984984687758944155818923662150578208746238894393577097596933816901399078617463316332861087812260480213313610385585170148762480877480377698010633747842003425777171012635315939166364466513019420346661685887557872065839736629132505802075822875396741377694500918089173843789526174839060321832022100268187243257213917173221983445662947146747809251663111881830886870180454979426716332773356700423545040000189379843309371468459260828296151157054634095231514373653361915789381498348538500889098973984825991010648504425961736
# c = 2390287440151859074977431224934228871908658589114219437055778330078017256080407294950854031769415044849530500106107973064442224774416776613372272028520897887714853438411971741352120204280926215575627696198467787476776488046304855144648477611586181055760370743447167004437637149018261023077103394738526455699389273400155393224849043765105308958801039850369697369041520212713853838096565717144295998444842703204720418647454216996934227195023472168304089615094827736108547722389920595345321889908810804579094914929760431468622186030462158492820207844856615479267999739548998939564881663449866169651403298987670586488132
           

2.分析

（1）关系

g i f t = l c m ( ( p − 1 ) , ( q − 1 ) ) g m p y 2. l c m 求 最 小 公 倍 数 n = p ∗ q c = m e m o d n gift=lcm((p−1),(q−1)) \quad gmpy2.lcm求最小公倍数\\ n=p∗q\\ c=m^e mod n gift=lcm((p−1),(q−1))gmpy2.lcm求最小公倍数n=p∗qc=memodn

（2）gift分解

使用factordb分解后

g i f t = ( 2 3 ) ∗ ( 3 3 ) ∗ 7 ∗ 23 ∗ 2393 ∗ 3527 ∗ 366844981 ∗ 4239635497381713295389892400206970088940526862906221142289989395161003862445657532681767202433617738214192912895683653509966318229692205594824730782240084535231334756734894990072459213137263718990462085235607508258139455347863193000273132715190230545146036560969125449733678167661544466914894540240251265112703244549027939551613246334667688651001165601808026013575023826682767609519039074312879093203583787588123968074115361950591800100181495674695323772760660431930353490999166741827737424350966329758499598188965617033800486795522806209067208021106016749374761086827893729835385130195191968521 gift = (2 ^ 3) * (3 ^ 3) * 7 * 23 * 2393 * 3527 * 366844981 * 4239635497381713295389892400206970088940526862906221142289989395161003862445657532681767202433617738214192912895683653509966318229692205594824730782240084535231334756734894990072459213137263718990462085235607508258139455347863193000273132715190230545146036560969125449733678167661544466914894540240251265112703244549027939551613246334667688651001165601808026013575023826682767609519039074312879093203583787588123968074115361950591800100181495674695323772760660431930353490999166741827737424350966329758499598188965617033800486795522806209067208021106016749374761086827893729835385130195191968521 gift=(23)∗(33)∗7∗23∗2393∗3527∗366844981∗4239635497381713295389892400206970088940526862906221142289989395161003862445657532681767202433617738214192912895683653509966318229692205594824730782240084535231334756734894990072459213137263718990462085235607508258139455347863193000273132715190230545146036560969125449733678167661544466914894540240251265112703244549027939551613246334667688651001165601808026013575023826682767609519039074312879093203583787588123968074115361950591800100181495674695323772760660431930353490999166741827737424350966329758499598188965617033800486795522806209067208021106016749374761086827893729835385130195191968521

（3）数学原理

∵ 最 小 公 倍 数 ( p , q ) ∗ 最 大 公 因 数 ( p , q ) = p ∗ q ∴ g i f t ∗ g c d ( p − 1 , q − 1 ) = ( p − 1 ) ∗ ( q − 1 ) = ϕ ( n ) \because 最小公倍数(p,q) ∗ 最大公因数(p,q) = p∗q\\ \therefore gift∗gcd(p−1,q−1)=(p−1)∗(q−1)=ϕ(n) ∵最小公倍数(p,q)∗最大公因数(p,q)=p∗q∴gift∗gcd(p−1,q−1)=(p−1)∗(q−1)=ϕ(n)

（4）最大公因数范围

gift的二进制位数为2042。

n的二进制位数为2047，因此gcd(p−1,q−1)占5bits，因此最大公因数的范围（十进制）为[4,32]。

在此范围内遍历最大公因数的值，然后与最小公倍数相乘得到ϕ(n)的值，再有e, ϕ(n)求得d，然后就可求得明文。

（5）e不是素数

e 值不是素数，分解可以得到

e = 2 ∗ 27361 e=2∗27361 e=2∗27361

所以，在计算时，需要将原先的e值除以2才可以进行常规的解密操作。

8. 值的变化可通过以下表达式体现

c = ( m 2 ) e / 2 m o d n c=(m^2)^{e/2}mod n c=(m2)e/2modn

所以解出的明文需要开根号再转为字节流

3.完整脚本

#!python3
# -*- coding: utf-8 -*-
# @Time : 2020/12/11 0:39
# @Author : A.James
# @FileName: exp1.py
import gmpy2
from Crypto.Util.number import *
e = 62674
# e = 2*31337
n = 10955952193867109007049171223448361703270316163381595475808977909570592186241572786000524779399251175639632506214659739654167891613877009909733465445850342326411605633577886819119591988666107494251525119526649254044083570299541059529064752255209948208082218652104303247582539992747196312466088319880461301389139117606269407703870835019991154758699118376408730038824561166793173838184174470555371713764515850687815448410533112337309598350391951304786480700678337420633644297059882623208007530826126677786131600580363410319193803307063974046834458230446741602905632962163026760269893441525950972199909583357468982874081
gift = 456498008077796208627048800977015070969596506807566478158707412898774674426732199416688532474968798984984687758944155818923662150578208746238894393577097596933816901399078617463316332861087812260480213313610385585170148762480877480377698010633747842003425777171012635315939166364466513019420346661685887557872065839736629132505802075822875396741377694500918089173843789526174839060321832022100268187243257213917173221983445662947146747809251663111881830886870180454979426716332773356700423545040000189379843309371468459260828296151157054634095231514373653361915789381498348538500889098973984825991010648504425961736
c = 2390287440151859074977431224934228871908658589114219437055778330078017256080407294950854031769415044849530500106107973064442224774416776613372272028520897887714853438411971741352120204280926215575627696198467787476776488046304855144648477611586181055760370743447167004437637149018261023077103394738526455699389273400155393224849043765105308958801039850369697369041520212713853838096565717144295998444842703204720418647454216996934227195023472168304089615094827736108547722389920595345321889908810804579094914929760431468622186030462158492820207844856615479267999739548998939564881663449866169651403298987670586488132
#gift = (2 ** 3) * (3 ** 3) * 7 * 23 * 2393 * 3527 * 366844981 * 4239635497381713295389892400206970088940526862906221142289989395161003862445657532681767202433617738214192912895683653509966318229692205594824730782240084535231334756734894990072459213137263718990462085235607508258139455347863193000273132715190230545146036560969125449733678167661544466914894540240251265112703244549027939551613246334667688651001165601808026013575023826682767609519039074312879093203583787588123968074115361950591800100181495674695323772760660431930353490999166741827737424350966329758499598188965617033800486795522806209067208021106016749374761086827893729835385130195191968521
print(len(bin(gift)[2:]))
print(len(bin(n)[2:]))

# gift * gcd = (p-1) * (q-1)
# gift % gcd = 0
for gcd_val in range(4, 32):
    phi = gift * gcd_val
    try:
        d = gmpy2.invert(e // 2, phi)
        m_2 = pow(c, int(d), n)
        flag = long_to_bytes(gmpy2.isqrt(m_2))
        print(flag)
    except ZeroDivisionError:
        continue
           

4.get flag

flag{supplement_of_rabin_algorithm}
           

结语

据说是小学数学， 最 小 公 倍 数 ( p , q ) ∗ 最 大 公 因 数 ( p , q ) = p ∗ q 最小公倍数(p,q) ∗ 最大公因数(p,q) = p∗q 最小公倍数(p,q)∗最大公因数(p,q)=p∗q

反正我是不记得了。。。。