爬过小山去看云
密文：ymyvzjtxswwktetpyvpfmvcdgywktetpyvpfuedfnzdjsiujvpwktetpyvnzdjpfkjssvacdgywktetpyvnzdjqtincduedfpfkjssne
在山的那头，有3个人，4只鸟，19只羊，11朵云
在山的那头，山-hill加密，加密矩阵[3, 4, 19, 11]
用在线工具进行解密，得到：
yourpiniseightfourtwozeroeightfourtwoonezeroeighteightfourzerotwofourzeroeightfourzeroonezeroonetwofourx
得到数字：
842 0 8421 0 884 0 24 0 84 0 1 0 124
notflag
大写提交
云影加密，只含数字84210，0作为分隔符，每组数字相加，对照字母表。
Normal_Rsa
from Crypto.Util.number import *
#from shin import flag
m=bytes_to_long(b'HDCTF{0b3663ed-67e4-44e2-aee7-7c2d8665b63c}')
e=65537
p=getPrime(256)
#q=getPrime(512)
q=6704006258427795304220450411280948926213189680360135534636452074716135019217911134480777251273836898349926894302122011679095979445240343891749741039976761
r=getPrime(512)
n=p*q*r
P=pow(p,2,n)
Q=pow(q,2,n)
c=pow(m,e,n)
print(f"P = {P}")
print(f"Q = {Q}")
print(f"n = {n}")
print(f"c = {c}")
'''
P = 6773247693445539441213578786581644136043035242620265251725630106817272212428325283262417364786451280269516220237289567904055371962564710888510272312707201
Q = 44943699913039047357456835559925378512493523252980366265686899925123157887149890185055864945749408514100461655676474535153113631214288057465776668291975220848776401405531599573114898492452990847774628035552581539370236080368457643523158920565504112005843410442573511095306233906498204203659537135943420051121
n = 4785613888465991171479248142015453309149548888755453367991501772592797686075465426815591528773123474962122102667475893532087343900904799831474817826058951265607078893487357878501280782935653048309499430170214015422492927323961394806106719569168457890040223027119115392961801582406287167644266319898276785787730947633037300317098453409851410936140488150390919951503767522517809035474567
c = 2247027561636791381460194811205520085150851211795956750955965051548230844233212462525163107917067768507367576366327035846089534916090521357212722275045521111077106695721780943857231570836500588468487620819893688830570842176795906808347617421353983094639290979158413935035603633331786978227439155042365130799647385116773171906670409535157184391352888875130028955334874727206292146950544
'''
直接给了flag，出题失误吧，不管，得知道怎么做。
发现$pow(q,2) < n$，且p是比q小的，所以直接对P开方得到p，接着正常RSA，有三个因数，发现flag不对，求了下$gcd(e,phi)==e$，两种方法解决：
方法一：
进一步尝试发现，不互素是q导致的，$gcd(e,(p-1)*(r-1))==1$，可以用p、r解：
phi = (p-1)*(r-1)
d = inverse(e,phi)
m = pow(c,d,p*r)
print(long_to_bytes(m))
#b'HDCTF{0b3663ed-67e4-44e2-aee7-7c2d8665b63c}'
缩小运算域能解的原因是，原始模数n超过了能刚好加密的模数的大小，这个得试。
方法二：
AMM开根，做的会更复杂，但有助于我学习AMM，学的还不透彻，待补充。
Math_Rsa
from Crypto.Util.number import *
from shin import flag
m=bytes_to_long(flag)
r=getPrime(1024)
assert r%4==3
p=getPrime(1024)
assert pow(p,(r-1)//2,r)==1
q=getPrime(1024)
e=65537
n=p*q
a=pow(p,2,r)
c=pow(m,e,n)
print(f"n = {n}")
print(f"r = {r}")
print(f"a = {a}")
print(f"c = {c}")
'''
n = 14859096721972571275113983218934367817755893152876205380485481243331724183921836088288081702352994668073737901001999266644597320501510110156000004121260529706467596723314403262665291609405901413014268847623323618322794733633701355018297180967414569196496398340411723555826597629318524966741762029358820546567319749619243298957600716201084388836601266780686983787343862081546627427588380349419143512429889606408316907950943872684371787773262968532322073585449855893701828146080616188277162144464353498105939650706920663343245426376506714689749161228876988380824497513873436735960950355105802057279581583149036118078489
r = 145491538843334216714386412684012043545621410855800637571278502175614814648745218194962227539529331856802087217944496965842507972546292280972112841086902373612910345469921148426463042254195665018427080500677258981687116985855921771781242636077989465778056018747012467840003841693555272437071000936268768887299
a = 55964525692779548127584763434439890529728374088765597880759713360575037841170692647451851107865577004136603179246290669488558901413896713187831298964947047118465139235438896930729550228171700578741565927677764309135314910544565108363708736408337172674125506890098872891915897539306377840936658277631020650625
c = 12162333845365222333317364738458290101496436746496440837075952494841057738832092422679700884737328562151621948812616422038905426346860411550178061478808128855882459082137077477841624706988356642870940724988156263550796637806555269282505420720558849717265491643392140727605508756229066139493821648882251876933345101043468528015921111395602873356915520599085461538265894970248065772191748271175288506787110428723281590819815819036931155215189564342305674107662339977581410206210870725691314524812137801739246685784657364132180368529788767503223017329025740936590291109954677092128550252945936759891497673970553062223608
'''
一种方法是对$a = p^2 + r$构造多项式直接解p
PR.<p> = PolynomialRing(Zmod(r))
f = p**2 - a
res = f.roots()
print(res)
#p=135098300162574110032318082604507116145598393187097375349178563291884099917465443655846455456198422625358836544141120445250413758672683505731015242196083913722084539762488109001442453793004455466844129788221721833309756439196036660458760461237225684006072689852654273913614912604470081753828559417535710077291
另一种方法：
利用二次剩余，求$r \equiv 3 mod 4$下的⼆次剩余a所对应的模平⽅根p。
套用Tonelli-Shanks算法里的公式：$p = a^{\frac{p+1}{4}} mod r$
这部分需要加深印象。
p = pow(a, (r+1)//4, r)# r ≡ 3(mod4) ===> p = pow(a,(r+1)//4,r)
if not isPrime(p):
p = r - p
q = n//p
d = inverse(e, (p-1)*(q-1))
m = pow(c, d, n)
print(long_to_bytes(m))
转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 1666739907@qq.com