首页
论坛
社团
我的

ADSKN论坛

 找回密码
立即注册

扫一扫,微信登陆

开启左侧

进阶RSA算法

[复制链接]
 楼主| natural 发表于2022-7-27 23:12:30 | 显示全部楼层 |阅读模式 | 来自 辽宁省抚顺市 电信
首先明确几个式子的含义: a ≡ b (mod n):a和b关于n的模是相等的,或者说a和b对模n同余
eg:
7 ≡ 4 (mod 3)
7 ≡ 1 (mod 6)
如果a≡b(mod n)满足,那么下式一定满足
  • a i ≡ b i (mod n)
  • a + i ≡ b + i (mod n)
  • a·i ≡ b·i (mod n)
如果有x*y=n,若a ≡ b (mod n),则有a ≡ b (mod x)或a ≡ b (mod y)
且满足a ≡ (k1·x + k2·y) i (mod n)
根据乘方的多项式分解可得:a ≡ [(k1·x) i + (k2·y) i] (mod n)
费马小定理的两种形式:p是一个质数,而整数a不是p的倍数
a^(p-1)≡ 1(mod p)
a ^ p ≡ a(mod p)
上题hhhhh

[GKCTF 2021]RRRRsa

这题的flag是用两个质数对(p,q)加密的。然后p是用两个质数对(p1,q1)加密的。然后q是用两个质数对(p2,q2)加密的。真狗hh。而且不能方便的直接用yafu-x64进行分解。。
多的不说,上图,鬼知道总结这图废了我多长时间2333

上代码:
```

import gmpy2
hint1=23552090716381769484990784116875558895715552896983313406764042416318710076256166472426553520240265023978449945974218435787929202289208329156594838420190890104226497263852461928474756025539394996288951828172126419569993301524866753797584032740426259804002564701319538183190684075289055345581960776903740881951
hint2=52723229698530767897979433914470831153268827008372307239630387100752226850798023362444499211944996778363894528759290565718266340188582253307004810850030833752132728256929572703630431232622151200855160886614350000115704689605102500273815157636476901150408355565958834764444192860513855376978491299658773170270
n1=75003557379080252219517825998990183226659117019770735080523409561757225883651040882547519748107588719498261922816865626714101556207649929655822889945870341168644508079317582220034374613066751916750036253423990673764234066999306874078424803774652754587494762629397701664706287999727238636073466137405374927829
# key_kq1=pow(2021,202020)*hint1-pow(2020*(hint2-212121),202020)
# 此表达式计算量很大,算得很慢,网上的wp的表达式与此不一样
key_kq1=pow(hint1,1,n1)*pow(2021,202020,n1)-pow(hint2-212121,202020,n1)*pow(2020,202020,n1)     #进化后的表达式23333
q1=gmpy2.gcd(key_kq1,n1)
print(q1)         
# q1=10866506913047038137740935566742708261832434856649253065298695652571582985605691427640899414330824525161279752924895740377208318584484168722588418228539943

hint3=25590923416756813543880554963887576960707333607377889401033718419301278802157204881039116350321872162118977797069089653428121479486603744700519830597186045931412652681572060953439655868476311798368015878628002547540835719870081007505735499581449077950263721606955524302365518362434928190394924399683131242077
hint4=104100726926923869566862741238876132366916970864374562947844669556403268955625670105641264367038885706425427864941392601593437305258297198111819227915453081797889565662276003122901139755153002219126366611021736066016741562232998047253335141676203376521742965365133597943669838076210444485458296240951668402513
n2=114535923043375970380117920548097404729043079895540320742847840364455024050473125998926311644172960176471193602850427607899191810616953021324742137492746159921284982146320175356395325890407704697018412456350862990849606200323084717352630282539156670636025924425865741196506478163922312894384285889848355244489
# key_kq2=pow(pow(2021,202020)*hint3,212121)-pow(pow(2020,212121)*hint4,202020)
key_kq2=pow(hint3,212121,n2)*pow(2021,202020*212121,n2)-pow(hint4,202020,n2)*pow(2020,212121*202020,n2)
# key_kq2要和n2进行最大公约数的计算,key_kq2很大,先将其对n2进行模运算不影响结果
q2=gmpy2.gcd(key_kq2,n2)
print(q2)           # 数很大,计算时间超时了。可以用模运算的相关性质进行化简来提高效率
print(n1//q1)
print(n2//q2)


```
>参考资料
费马小定理中国剩余定理(CRT )
[GKCTF 2021]RRRRsa_Mango|Feng
[GKCTF 2021]RRRRsa_crypto
[GKCTF 2021]RRRRsa_lrving-



本帖子中包含更多资源

您需要 登录 才可以下载或查看,没有账号?立即注册

x
 楼主| natural 发表于2022-7-27 23:13:15 | 显示全部楼层 | 来自 辽宁省抚顺市 电信
上代码2hhh
```

q1=10866506913047038137740935566742708261832434856649253065298695652571582985605691427640899414330824525161279752924895740377208318584484168722588418228539943
p1=6902269328980601949219613176450133921217522327053564675874794684208098887430842411945865158339970723735249329423163885462814392041137323120169984167556003
q2=9677269841262626154014538802932467267491753397490444024091702336017847934813782962738462815968445258898876277887404901976123237057034767859042412249801889
p2=11835561570786175452289950631688760569243828783751730060395260636838089311102167070897024394962805370154566853456342966948392591084922726455535034951183401
e=65537
from gmpy2 import invert
r1,r2=(p1-1)*(q1-1),(p2-1)*(q2-1)
d1,d2=invert(e,r1),invert(e,r2)
c1=68111901092027813007099627893896838517426971082877204047110404787823279211508183783468891474661365139933325981191524511345219830693064573462115529345012970089065201176142417462299650761299758078141504126185921304526414911455395289228444974516503526507906721378965227166653195076209418852399008741560796631569
c2=67054203666901691181215262587447180910225473339143260100831118313521471029889304176235434129632237116993910316978096018724911531011857469325115308802162172965564951703583450817489247675458024801774590728726471567407812572210421642171456850352167810755440990035255967091145950569246426544351461548548423025004
p,q=pow(c1,d1,p1*q1),pow(c2,d2,p2*q2)
r=(p-1)*(q-1)
d=invert(e,r)
c=13492392717469817866883431475453770951837476241371989714683737558395769731416522300851917887957945766132864151382877462142018129852703437240533684604508379950293643294877725773675505912622208813435625177696614781601216465807569201380151669942605208425645258372134465547452376467465833013387018542999562042758
m=pow(c,d,p*q)
import libnum
print(libnum.n2s(int(m)))


```

回复

使用道具 举报

公告
  • 问题反馈请扫码加入一期核心用户群
  • [学生认证] 认证后获取生活类板块发帖权限
高级模式
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则 需要先绑定手机号

QQ|Archiver|手机版|小黑屋|ADSKN短链接收益平台 ( 冀ICP备2021002162号 )

GMT+8, 2022-10-5 16:56 , Processed in 0.319003 second(s), 17 queries , Gzip On, Redis On.

Powered by Discuz! X3.4

Copyright © 2001-2021, Tencent Cloud.

快速回复 返回顶部 返回列表