关于题目more_calc的一些思考

gclome · 发表于 2021-1-11 19:26:13

本帖最后由 gclome 于 2021-1-11 20:05 编辑

原文链接：关于题目more_calc的一些思考看雪似乎不支持数学公式的渲染(还是我没找到?)
数学公式都用图片替代了,好难受.
题目:

import gmpy2
from Crypto.Util.number import *
flag = b"flag{xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx}"
p = getStrongPrime(2048)
for i in range(1, (p+1)//2):
s += pow(i, p-2, p)
s = s % p
q = gmpy2.next_prime(s)
n = p*q
e = 0x10001
c = pow(bytes_to_long(flag), e, n)
print(p)
print(c)

复制代码

思路1:由于p高达2048bit,所以极有可能m < p

当m < p 时,下式成立

c = m ^ e mod n
c' = c mod p = m ^ e mod p

复制代码

于是,我们相当与把q给消去了

构造出了新的rsa加密且满足:

n' = p
phi' = p-1
c' = c mod p
m' = m
e' = e

然后一个简单的解密即可

#!/usr/bin/python
import gmpy2
from Crypto.Util.number import long_to_bytes
p = 27405107041753266489145388621858169511872996622765267064868542117269875531364939896671662734188734825462948115530667205007939029215517180761866791579330410449202307248373229224662232822180397215721163369151115019770596528704719472424551024516928606584975793350814943997731939996459959720826025110179216477709373849945411483731524831284895024319654509286305913312306154387754998813276562173335189450448233216133842189148761197948559529960144453513191372254902031168755165124218783504740834442379363311489108732216051566953498279198537794620521800773917228002402970358087033504897205021881295154046656335865303621793069
c = 350559186837488832821747843236518135605207376031858002274245004287622649330215113818719954185397072838014144973032329600905419861908678328971318153205085007743269253957395282420325663132161022100365481003745940818974280988045034204540385744572806102552420428326265541925346702843693366991753468220300070888651732502520797002707248604275755144713421649971492440442052470723153111156457558558362147002004646136522011344261017461901953583462467622428810167107079281190209731251995976003352201766861887320739990258601550606005388872967825179626176714503475557883810543445555390014562686801894528311600623156984829864743222963877167099892926717479789226681810584894066635076755996423203380493776130488170859798745677727810528672150350333480506424506676127108526488370011099147698875070043925524217837379654168009179798131378352623177947753192948012574831777413729910050668759007704596447625484384743880766558428224371417726480372362810572395522725083798926133468409600491925317437998458582723897120786458219630275616949619564099733542766297770682044561605344090394777570973725211713076201846942438883897078408067779325471589907041186423781580046903588316958615443196819133852367565049467076710376395085898875495653237178198379421129086523
e = 0x10001
d = gmpy2.invert(e,p-1)
m = gmpy2.powmod(c,d,p)
print(long_to_bytes(m))

复制代码

思路1的推广:

且满足∀ m < pi ,(1 <= i <= k) ,则

c = m ^ e mod n
m = c ^ d mod n

复制代码

等效于

c' = m ^ e mod pi
m = c ^ d mod pi

复制代码

其中 i 满足1 <= i <= n

即只需要知道n中的一个素数即可解密
一个例子:CNSS Summer Camp 2019题目:

2
3
4
5
6
7
8
9
10
11
12
13
from Crypto.Util.number import getPrime
from FLAG import flag
flag = int(flag.hex(), 16)
num = 6
e = 0x10001
p = [getPrime(1024) for _ in range(num)]
f = open('cipherlist.txt', 'w')
for i in range(num):
for j in range(i + 1, num):
for k in range(j + 1, num):
n = p[i] * p[j] * p[k]
f.write(hex(pow(flag, e, n)) + '\n')

复制代码

2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
0x8f83bbd164fea268a30bcb4715045d83aa8ff882795f19149a19edeeb5543c845b09669c1448047722dfba93160e1b1b9513439808d2dcc898980b5fcaca8e103033b64faf3670448ad03e8c4929c5b381f2b5f8068c97612d04d819ad2bdbeb7fe1aa39cf569a19c3e6e400a8f7d239187df89f1325d8b38e487a183cca7a95295b5bf9f59ade348c338da8430ec1bcf45870898e458d7a07de5a55748f2eb94b357f878c6ef14198839615ec71a7bfdd6de265144a016f26d816d7d5838f750a26416559095acf7def0407fb01ee0198dad1088ad0eccad9342f21a4e02c5bbe2b53813db060bc7d6c134835af8cae696ceab3483820704a28548ba109127d42b197f97a242a84eca20ff2e495eabd52be86d6fcf1cefbdcdebc2b533e9dc7b2f10eef53dbef2237edfc2a47de4e2e1fee555440ae39136cfdb24a643772e536901091607abf030aa83894fb95c8076885e41282098ac82c5c7666bbc387ab6b64c87c10dad611ce3c4d8c884e52254b031fc4fd4931d0e9540a5cab1aa9f4
0x2dc31a1689ba766d73a11c19da4829ca8b42c250499a4c27d52574d0f7c53c3c355fc90654dba3acaddc4a0fda44ba8500e23e1e75e93597c359364cabb0bb522dddf68d80b26c1eae56002e2f66d71d3eb84da0fec44a459786563698a9a91d4f5f784983cc45b7c8f010c7160a416a863e0567b4076803a8e8439991a709a6014ed13f741663772e37122d24e4bca831c3119628cf83a5816969c150656f32d9236fc281fac8780116f3c250f597b1ef4d8dffee83b559c9a53cfd74853b5cfc5db7413e4daac9a5a7b264d18e9856e9c3e81edf989693a65db450b395a68ef7690c56ba93a134fc80c0065dd142256fe3aaf21ea534732f6d1c240d343fb6878e5ed347be733e1b58fba8857578ad7e3389c53c159becf4ca78f7a9c13db52c7328efd969e256ea70564e1d56f691925f37e9f9d87fe899e756fb77581065ec123601dceea2f5ea883beeaaadfdec3219ce0e10ea05edc0cadbdcd08b1c16484bdbced1c9d4059e99363023fceb2418231c1c7c5f8494247d23733ab0790d
0x281a805bc3f0922ca02aeb516ff0e42a87a50745d89b5725d977d533c2c119b7b590c58c95cdf467922088609866c83003766808adebbb10fa1c49d666692484675be1e74c986da24dd5ad8d7c6a62c5671c414044a7c3707bc074621d5d10d0ac0268bd90396c514e5e2742ba27255f5145bfada7398cf1233194f0a92f725c9a655bb9785b22f16fc9217dd00ebcec1f58eba97aec22decf7262499e9009e02ef8a95f711f1f78fb8515d0086653ef6bf96b5fb72365740b2a9670181ed79a6edbf324ad0a1e501af37e186e76e690a56f17dc0f8740f2d471162e366d6b6324c7d9762f85e935db406775463c6483462ec1ac14c2f3d9055ac9c41f6abfbb2716efd132b6db0b99498ac84bbb3edf7a449d95ce2051a34bbef683bce66209185d182c726964ab07751392f373c71e4af73b1608cee4fc97c63d640f84bfc5dbf22fddddef5eba956976e5d2228ad423feb38d189602f1581af8ec5be3594afbbe55cfc4e0b2f6946adc56d9480d90fdfb0646217fe7a53426bdb6d447ebd2
0x48f2c2cee8f3c8b0e96a83569156b904e7836bcc3b5bde9ea4fe7bfb5bf1c992069be704497dfff6fd91f693932f119dcf724b564686ee4725b8cb4aadf42dcd9daaa5cb31d294e003f7d2d1953e97b4cc7a71590b3a726b15970d4e56916eb81b9e6578bf4b2558bedccb75fabb92cb52302694b4a95194d1f3f0fd31d779006c0d388d26555f1337b0e5287962587d461a523ae9d0a31428aaeef4254362d515a4d39cee8202b3290fbab1ee8f21a8ea5971087a742d67ba7d4896a203f7a93c7c641a7aedcc1bc62a8397d40738714ce33c614ab7acc567c14136a4175f071a707ca42671a7edd63d54cf6a7809cf72bda56ca4f1d61ffbcc2b1f2e4c72939b60a860dee236c7ed28ea6af538f1c823c4c98e3a4f03ef45d21ac8f4cadb91523449e31b688d99613e712dcd00ad7dcbee8370e587de3afd8d9526c7e2cbf61af1735b7401eb7be6d61cceec4839bf81d84da7839794c4e14e30745cc0be00d1ace1003239d4e075ea985ff8bbcc2735bfbd5f09b93f78ee5cf77517815efb
0x372a2aa70f441f13d1e3a93b8046d86649dbee1184e72b4c7949ee39af24196adc75286f25c0df068a2950259994b11c8ce40a1628e2fa6ea6577e4858342be639f54e3530aefdc027a93fed9ca2a5289b5b0d4e2ba560531ede93a4257853cc907251a47fa2ad07cc58005061ef6c726e0e2e47d5d73b3df6fc61fd734c6b1d264e767198554379f6da9e91407bbf03d535d620bf318ee97e1b4710335f5df646b0cfd277cf62ff9a950004b188d7609ed3f513808774f4be732c4f2d478ad4599bfe0929418c4dbbe7ba69cc7da0032ab8f6beae730fb200a3ebe9d1f6bbe4ea4ce3e130fd13bef0733ef3070fb54bc2b6afb0531b05adab315480a3640969f0d147b7d5bd70ba1ddc3fced7d5d85fa5eaab0d9e7fe4aa649f9a7557cc9c1e532dfbdc22d4c621b9d9147990b13602469afe243372e62e58e513bfa0e7588a9612a62def541979d13375e06ccf28e0b8b7f5c22e8bec26bf26c0ed221d1c5fc1b420a98d180e49f1310bd44c5c2cd19a0f1bf0ffed6a678e136f19041cc93b
0x38cf70f149fbe50b1a8892ebed5834696bd79781e3238a8331481c870fb4536e25f6bf4c7571b478a01389c8bd8c77614958c1a2953a39960174b4b60ded7de06d179a4a93e1ab48438b4a4c8273e4fc716119d4f4e9e5687a5d6001a8de1486b6db5a5344172504b63180b92ef0a487cfb57487b9e7201c5c39c17a23ccd8f0168a184ec31d184b24a5de4a4f13050b4312c251e99dcd57982f4eba5d6095bd1fd7d7cc62bccb6935212153623673e227b06e2c9b083cb2351a5cbf886d7d70c5823705a5027b03436c228d9bebd85f31465bc82e7ea85eeafaf45b847a57d9951f4d8fab0f8e3009d58778bca9b747feeba09f858f988c27e6dde7c643c01b2ec79c94cddcf94b73d6523a45f1170c817f30f1c3ba8bcdd9abdb3e4d68be20450dbfc9d3b2e271a77371c22f8a02dc30f530f31a755d496e5e9f7a64e5418fb8a803d66b15120679271596b74bdb176123cdbe1c6b0eee9bc072a04cced59b6e8a920430d9a91ac0bdee6b2b00dd4965c7b3941c728f4e03acff0067bdb476
0xd3bce59b15f87b90f043e1f1043f025e5bf9ef1460a8366c485826083ad4ca93c4344d499fc9daf318a99d442e478117f379e3908812d2472a7ff5aea596cd6e2dbafac85cb6f0d3f4e8d1324b283c56f30a78f476f00ac26de02459b4c7e3d17d125339eddc47e4300e930a5af18df8811c2c4904405bfaac84a2c6df7feb5254a7b8fe642f130ce9af57ebb50ca773a2dc76c53d9fa7b48e89ede8a84f29e859452ccd41d7cff1de6a756cce5a34f514e02c7ad11bfb2689c1581b6098d3fef1551be7c430dd6bc1baf624a8966504850921062861a60e5e90a6ea3ce8af257d923556a969a5d2badc4e01cf7a23b739b43ce68d4a3f98236ab54ab06e35ac78ac8d295357e23080e411a50b7e47bc1418a4b1cc9c30848dd9a8a02241455b4e58f6b4e47f59f062aa6ef0942a4d83062a3660c24171d6d7d70a6e57552fbb46b76394e61651a84d84fa06782773c872cea4d51fcc2b66fe56dea77c4c88b1bf036dcc937cb83371126566c817fd856154fa85b908434093308aaf8c01214c
0x4fa377d624afca3fc0003df5d117d79e9f951d2f47d3b90c7e254fd120f7cae34915b251f629b182bfee2977213e68a8c9f6be698d15ab8fa82c7e26b5d7890d2eeb4cfde4eab5e85ef6e9f6a8b9bcda7036f1a8af6846a620c64cc1555ff1824579bbfd4e51f0aebb825e652195a10f792acf69c347fae73a53cafd986d2262b8e7e1acd6b42a1f995558e44c2a025b96a0f61f594e44ebed1918d9e788370c69b7c73eff8ddb4f4c386258093dc8263567fa69702f745d9ae33bee7b76976a7a8b5548be810b50d08f24b5ce251cd7c9af42a8cf46ebb48106ba8dea9e0a12377ac075613b70ea321a677ae5a44548cf5485ee85290445c748bef9e1e339f9a4457225028d4ea08dca676eda38cd0525b1dbfb7a41bd38eee6cb9be654e867d75a9b7150c3c0b31a3c5355db45a7daf9eff8849b1acf8c2697452301e65673c719972a9d9e240050508bee598f4829d8af04b57de2199ee6fedf91f7771a746321edd09b044c636b7de0bdb15d74346e1f32ec3626173e4afbdfbf84055393
0x5b62ebe08e5b82148b5776aacce6c61dc0ff4a3242cc4fa86b1b8005427076f4613544d8c3059da6d892119ff5466089c13aafd5adede63f39721620d7823b469c12aed78aa5c26b19514e8d5be356812d18c42207d65f53e34eeb2cd6ce559fddd9a0c6a5f36c25cc8a3be399b82a2e20f81ef1d6a495ca9e983738244ada51f97901aace2b4dd432eb142c90e78927ed1e6e2c81b09683c37b8c3716d090493ac19179b89abcd0e60d17768a4db9a52cb30fd74d8b6c939cb7e8128029d30e1b39f8dc14a984beba7520a0e172286210c0ce73b7da94130e61b5bdd2b3927fa0ac56d5067abc26454b4b446947eec81972c04b4d155e6eabee682182ced590b55de99dd1c8cfab12512670fc8ac583ced1a9d6d880859593dd7af6ac0ee6eb13673287ddb90583019489c20f83857dd394845e2d2cdbae71f892c94d0660576a5d94614cbfd741b2ae30536aa27a59d29c3d1e948488e04b68832d096a6ed319703e6b70020e2bdedfc9e44f953036eacb403a5d4e927c0d3f2779290752de
0x1229940cb26d30cfde2f3bd76875ae8723101849bdaf8472a4a608e934f55a60a113ad1aea82a2c86f22b4d31b64defb2a6be8466558081d46d3a1b686fe4c3f8c70893c6fa69eccb055a08167f5e11dd7cc2da26183a6a118653c6dd762d48e7b658549f3f78be2904dfbefdecefb4c8496174fc0087d0705b22925ef6563ff8fe42b3017dbc577fb4ab27c80208a5905cdcb28dad026b8e0dcba325edac48843e8f694920f6637e02d758a07f31e128c289d98625cb0695ab81eb6355637e78ae6c43bb58cc05ff6be458dc8f6e7766b6097780b05b63a580619e857eaa3e70ab8b0eeeddf0699d2c04cc18f5b2b19ec617014da47b7b6d8dd544ea02e85022ee59b88d5b81f7e50b67b469c4f98ca472988077653fc80e73363a8b7a53aca1c0f0d54acccd1b2f42f2fe3f295d3c50505791614aa57b3626ed18df7871bea968a4742515b3827d8d1602b22206b36496f7fada7ca6dd1aef935a1349bd22e186302c068ce527314d2ea2c7f7bcd9e06e1963b539d864ef0394e446bbaef7
0x3dbc94af875b11e51cfed96cd640b3f39be138895d3fb1862355936e11f031c13d73520b335d9c97ddc39218bc04166f82ae490445b7a9591deab89a8323e04f4da83c17d915ce7534b5d4745d71e9675919bf45c29fc49e0cdc56f5ad5e15744398029c0c6b6754c07d3610342805d572a50dcd9d00b2a7e2521f96b095d27a0501c9fede3af638e9a3e21feabfc035834ec6b4065d88b156245782cd212c1d79d96fbabb3eff27f3c3122f6421e60369e509a0ff0a55252c7b67f6ac73df2440a692ac57daedbeba56063acde55e8a01bbe3f66f7bb85ae9ebf77bd1ce99a549d3933d6797f258f11d774b28568e48cc3ac6820e837c5563600c1adefd2c36811a2856ffad79f1f08786d263f80bfe7c486bd6f0c8dc0c6dcd045a5f0b2d4d32dd5366a21e4e9f406d907fe0ad82aee05d124e6ced6a8fad5350cfc70a500d43478d68be892d32f35e5dfb283547649a69170510e5e2669b532e9e8228f76de36b91bb558378d77c328062061e34d57f7c341295c2555e5682645f23d8091b
0x31d1cee7a2202eb4264dd96fe68057e30a88520cf0eb856de2ae0d5cfb1731cd2a092b01cca28b31a8ef7878a1d976c321404323d0898f726a69696a987c08f4e7a7e835418adff3aa1fe30bab4ada7b89925d8a6f7fa0b984669bda103f2994306e49990d4b9f9d9be7935f03ac2d85f4cfadaa30bde7f5193610998a164323f001b88a77cdb0aedce8718d686a25c04b7f91351c6abc2be2133319b91726e0c2a8b53cab2b17ccf0fb0a2fe579b727cfc3686198180fd8d78cd68eb0c9ddcf7fd70b55d47719dd488dbcad28a287f3377602daaa6cc07785cdc55599dc750f85011048ad0261fd54e54abc1a92e66d3be9b8d15077088b7893c6ca083ea94f75880e8c6e8ddcafd8b260e2e5d993f3e73d7c80c6e7d47413b02295072fc235d61003e157c476d0b8dc7c2d846dc180b1cac72eed1da20938ac4afcb5627c124af8b2f05a9dbc6443d51a75e2dc803c67a8002a6d46651a8440bac8030f3d46d643bdd3372592bfe52b0931ecadfcf577564e4005bd0cf6a6bbedf1a7121fe7
0x9c9aa94f29498ed403832d8b7cdec6e3aefa21f22a44f0af8b90dfd40adc319b6950773f4464d3225231d47eede9fb8d76a515640755af5016874ef14f3ab526f47b66b7e32ac02e412598582479b7d2f6ed85dd5c35e7bd9a8f2903594d35483d1ebd021a80229d0492c65805e9f831ac3caf8354e0d7bf27f18138e2de07cc4d8a3915620519d6d727cc62ee0f818615221b6dedff09d587d0dc7c17e99e8979df5cbd30af9778ae79c42ea0a982b4e03d83021197430848392e5ab82c3f3e9a068cbebb4dabdc4a72c606497cff319c980ef3af84ff36c8d82741531f7cd717f81e50acbf0b791d04f6eeff2dabc259703a30a7f1976957d472234a6cf2df2f0707052ad468dbed17d14ab02678c44ef501083c4f83c56ebe3cffa5d6c70dc206678f2057e0f04138318190b09d1cb2696cf17428269401e72344c56311f9cba297c3ceba4d498e12c1a5be1cf65328c9f56d294653a9da68ef41d4a4ef4bacd3e8d26e136f6b56c422ce542411d49e70569434cd902b9baa54927bab8b03
0x41f291d82527251c9e0e60c19533847f85e8bbdfd6d68c78a3d2b8dda39f18fb8ce2245d5d40974e0ef5d5f5febca0f6c47ba0ce84d775c1a7319f352861a395d6071e9ba5d170a71bf54b6f1a5bb2571192a5294a7724e81a7077b3784dfe1859f242fd80088ea5eb9a65436841504c36e95214251fe81315139948802f584b9e69ca3e83cf8554d97597c9bb99847dca10e99a198beaffec903f5fe6915d8fd3877c4abc70dd52748eec05efeb5b0da50a690f509c9e13d0ad6157cf579956d18d757cc741df5662bcefed4441bc35c3a8d3eea7e25fa7e45d51cb099de4acf9500791a4077d1b9a4a37618b1f474421de928a68ebb9d2de55f4a2c4c3be53d3e0aa26d8dc22e5caa2ddb54169cd9cbb17a241098e8d2b5c0d23f7903d032de7da15b1ce49b9ac9ac76cfdc184bd52b70f4c008f974eadcbc9fa68978bb4041fdc6f61f110b106a18519751e64b78cb405cbb2ae4f9ce15d4e3613738ae24a3907127adbf0603b075bd1708c34df3ed5993bf31ac8a66a0440aef3217895ea
0x7e746ae63e55c80c7b5eb5968b582ed37370315c579b490b1776106dde972c25df324a4c263e58cf96890139927afbf732e4152e29fc6d598503518e460ee8ad5132d671dc82fb37760c90a0ac5c7cb2caf40e346e9cb287d86a2a3412863c533c9ce21e9fe8e580901bdf3a0fe4e6a6c262cd943a1dcc6b31ea8838af4537f4a70176c0154e0fba9d8fa414e1bb132c61435c4e8986f33ae34f514bc47afc96c2bbae0dc25dea6ea779c99ed06e92da229f0e5c16d6aa6f2b7f767b979ac7d44714d2d95e1718af0266100548322ff8fb492626782f9c54fc34b072a23d5da6bdc4212c402e2c4c999ab86350ced9dbaffcc32c868f1c5bc11d9610a66f82f2886a460b6220106621fa99fb0698bb7b4caf619c995c339ad50bda99902374d9bf46765de62cd047803e9294f70aba9bb0a991e618744142e2d458dd15c4df8f616f37726517acd5be7180d617e21486a1147545e6e21740531f939fef688c5283e084c7395e2695bd3d265fd18f16a7c961a24e0a4d55e0715dda01127b937c
0x82acf185accdef510be2f071667b1e038b135a1fe8514e1688f95928936a7064e2153b7890461f61f8e715fbdeaced90a8dfa9592fa92425ef467493f4c6d5f3995e9167c5e42736474db4cb487b0085f0b94032d96fc8302d5236a8885f7962f370f28e041250f459e908c1de4a27f6df0016be0e1624dd05041e43c733e4fbeb855128685c70c85a05e1f148891da4786c6c132ee908c63a39384ee828a04a5e58cdfebe21b45fb79e184083259dcec2c7a8e05d419c5372110163d20320a32e59c73a48aefd8079551a32007417dd6f147c8b39fed33e67e99e5cdeb754945ab00cb30cbf72db81948bdcca2cf06ac32ee9c0ea48a403c842f85a72acbb48dae07e7ec3dd1894ceedfba82e93d0d95264cdbd4b07e1c910fe899861a503714a34dd01417f2931e2d8d6fa66a3e597bb28167c9045803c9a9c9f12d3de8029b3aad38d82d353120be772afa32af9e5b7a80df6864435665651fa5061abac02272371dbddd324878240fcd51f97093cc579f8e38a98a0a43be48ba25bb001
0x62a6e17d4482b50a3a433ef3aed20487916ff87f77f06e8685be99cbc3de63dabcbd1a58c7fa882d929c35b1ff150b2af3258cc4627768511397fdbd51a2ce2e33e7d3173c6d1cd67d7cb0907173403e63376a4545c2953938d217f35b8e511fe980d3725441e1b7f6724d14d397ea8685069c912d1c4705caeecb02ceffccdf73cc3b4707a339c8d36c06925b7e96269ec12d291663c0afbfcc8d3a2c2bb92732cc328535b802489f1c04a5ff52158ca1da022c6dcf08e2725f6700e2c3d33cc7c9ff9c04e847ec52579adc106cc2520584ae3216665cd3a79fc51a15da403df3f439973b612be7b6d80d40bf6c67748f5595fce1155f31551d4901bf3ba69961f89d28acf9a2b1d1c51f7610b31c6cf8d782950f699668f1db72621f626836831d2e8f91bcfb8f8ccbb0afce2317f396ea773237f3b09b3f1c729e2cc6d36d8b3980f1849f5d5ef6419bc8605d08b61f67be9102dba66c645399864c0684b3228f838e36a79f97c67b5025d1e800ff389e0eb4cc1657251807f15482501047
0x400e86bd60fc7d01cb8331e87b4c7bd6b303731c9b4e8d245d34e564769810a251a341a5aa70e7370f0f641b0c62f16f0d8fef61dface09e297916dc65a60608f4ca02ac4be88dc6331f6ed2a091707d2ebc31c3cb0e734d7b3264c4aa389f0ef03a95035b934be0c10388784641dceee4fab0f5e6cc21435e7674cfb3a85ecb90b8e1e214280312be8eced167dffa3f3ce3c6a2bd918622c6d5f4cd622673da5989bdb1db2d21af0f45ca6be3c580592da7a92619aee5efdde462a1a8a2417b5abeedff1c166ddeae0b570cba48bf44b3e7299ac4a358dc30d9dc69dc2ab7077271392ef643f0fb2c0015afa33f06eb09e12c719c26977a49d71794e885fae866d15f1e96cf12b8b9dc9d5afa1f19b896babb35fc09f765c0bb4d6109bf49c6a72a85ba6239c4dccde553198c4a3a7ba004092975a707a872416f23485af19f50bc591b4593190a620d1de9dd983190a1fc7b4f3cf558057d4f342fdca9d765977f116620f140f72203d3b797d0d09f30fef3ba8bb0e1fe528338f57c1ab408
0x6490a1865e1c53cf274ad5f4a35bd51aac436e85801c6554ac058dd25f06be6f7a35230c268f4663eb37802aa97164012e724739da25de0392ed9b7aa869dd7c7ffd6e9fa7a34ab366e52717b9fd16bf27c2db5f7d66d8e27b923508da55629459b311b23224775ab278ac59b1c5f2bcf34cfecc03619f22c5c0bd972ddb9b59cac34c9531925cdfa7bc4ff0e19075b4f4be9d7dcf1dcbf05cb74c2afbfe4509335ff114a11ef0f5e883321c6a4b401eff7d3c7e7488298a8302b734ab063451d4834d13c419208bc5a61ff84efb6bb4b0077b3fb7313b2d1e8b325c195b1bb91d959ec3e718b2870ba2ea9bc07b57b93ba5e069c099da0ef68530c95d3ffcb3380f5c064cb14d4e25aab0f6016dff1d3ae38f31b618db2156088e7a96fc0e283b02a7a8a7b87e6c8618275dc9f26f1ddd4ca75e3961179ffbbee62fa663e106fde1a0b9992bb504afa04d7f412b30847dcdca53378c6fa2256e89ac92144fd3b24de3aef6416c15505c7768df60eb3a315ab373a8e03d971323ce2fae32932d
0x77ad4fb838ded1c35055c6cd8ceab0cf3401c1e0cfb89bb429396f5f1c0c9073e13b7b741c54aac29a506593cb45f332961251afbf549794d36aed1b1765e6c7732bcda39fb6af3857498fa5e2f1275957218016e70912e153a4232a2cd2605781a46db2872698e26c0887f5bec99847e8629196613d702020d08eff123bf4d4b89171bf860cdc04e5629c137fa948a2f220c3e8e8b3d1340251780c5e4cd2c03dfdf1b47b6c57afd2f65a7d443118db1c9f03f2cdf0c07af7e65f133214d7e8bc9550492a6331eb2d1d848ecc78ced742e2dc860141f039b9812ed5c1e8cc0e07c4842b91e3732d4c23536359c0e657ec192b033060023021eec1612d6b757f0dae34f587ddcd01297446820d4dc5f2d73be005f26ae2d30e64d744d333c5ab7f395bab41203fd2fce0f3fe31f2b5d206289f5b63b7e071bf51a814bbcf014a6ff3a0fa6895873bcc1f660bc4974d4cc43da7ad4fe2dd2720323058efe36ad7cc48a6480b85f7ec5ef371c82a9b952d358adc07a2d528e2945212908a6e69b8

复制代码

普通解法:题中首先生成6个素数,并且n由其中三个素数相乘得到

这道题,我们只需要想办法恢复素数集就可以解出了

我们知道每一组的密文和素数在素数集的位置

为了方便描述,我们令p中的素数分别为:p0,p1,p2,p3,p4,p5

于是,我们可以得到如下20个等式

其实'+'和'-'是一样的,为了好看,统一写作'+')

m^e = c0 + k0 * p0 * p1 * p2
m^e = c1 + k1 * p0 * p1 * p3
m^e = c2 + k1 * p0 * p1 * p4
.. ...
m^e = c19 + k19 * p3 * p4 * p5

以第一,第二组方程为例:
可以改写为:

c0 = m^e+ k0 * p0 * p1 * p2
c1 = m^e+ k1 * p0 * p1 * p3
c2 = m^e+ k2 * p0 * p1 * p4

作差可得:

c1 - c0 = p0 * p1 (k1 * p3 - k0 * p2)
c2 - c1 = p0 * p1 (k2 * p3 - k1 * p3)

对上式取最大公因式可得p0 * p1

(当然也有可能出现k * pi * pj的情况,不过k通常很小)

组合多组数据再次求公约数就可以解出原本的素数了

实际上,用密文的第一组数据的话,可以只求出前三个素数

2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#!/usr/bin/python
import gmpy2
from Crypto.Util.number import isPrime,long_to_bytes
with open('cipher') as f:
ciphers = f.read()
list = []
for cipher in ciphers.split('\n')[:-1]:
list.append(int(cipher, 16))
l = 11
primes = []
for i in range(l):
a = list[i+1] - list[i]
b = list[i+2] - list[i+1]
gcd = int(gmpy2.gcd(a,b))
if gcd != 1:
if gcd not in primes:
primes.append(gcd)
may = []
for i in primes:
for j in primes:
if i != j:
gcd = int(gmpy2.gcd(i,j))
if gcd != 1:
if gcd not in may and isPrime(gcd):
may.append(gcd)
phi = 1
n = 1
for i in may:
phi *= i -1
n *= i
e = 0x10001
d = gmpy2.invert(e,phi)
m = gmpy2.powmod(list[0],d,n)
print(long_to_bytes(m))

复制代码

简单一点的解法:由于每一个素数都是1024bit,所以有极大概率m < pi ,(0<= i <= 5)

显然有以下两个式子:

c1−c0=p0∗p1(k1∗p3−k0∗p2)
c7−c0=p0∗(k0∗p1∗p2−k1∗p3∗p4)

两式有公约数p0,可以直接解出p0来作为n

2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#!/usr/bin/python
import gmpy2
from Crypto.Util.number import isPrime,long_to_bytes
with open('cipher') as f:
ciphers = f.read()
list = []
for cipher in ciphers.split('\n')[:-1]:
list.append(int(cipher, 16))
e = 0x10001
n = gmpy2.gcd(list[7]-list[0],list[1]-list[0])
assert isPrime(n)
phi = n-1
d = gmpy2.invert(e,phi)
m = gmpy2.powmod(list[0],d,n)
print(long_to_bytes(m))

复制代码

思路2:

#!/usr/bin/python
import gmpy2
from Crypto.Util.number import long_to_bytes
e = 65537
p = 27405107041753266489145388621858169511872996622765267064868542117269875531364939896671662734188734825462948115530667205007939029215517180761866791579330410449202307248373229224662232822180397215721163369151115019770596528704719472424551024516928606584975793350814943997731939996459959720826025110179216477709373849945411483731524831284895024319654509286305913312306154387754998813276562173335189450448233216133842189148761197948559529960144453513191372254902031168755165124218783504740834442379363311489108732216051566953498279198537794620521800773917228002402970358087033504897205021881295154046656335865303621793069
c = 350559186837488832821747843236518135605207376031858002274245004287622649330215113818719954185397072838014144973032329600905419861908678328971318153205085007743269253957395282420325663132161022100365481003745940818974280988045034204540385744572806102552420428326265541925346702843693366991753468220300070888651732502520797002707248604275755144713421649971492440442052470723153111156457558558362147002004646136522011344261017461901953583462467622428810167107079281190209731251995976003352201766861887320739990258601550606005388872967825179626176714503475557883810543445555390014562686801894528311600623156984829864743222963877167099892926717479789226681810584894066635076755996423203380493776130488170859798745677727810528672150350333480506424506676127108526488370011099147698875070043925524217837379654168009179798131378352623177947753192948012574831777413729910050668759007704596447625484384743880766558428224371417726480372362810572395522725083798926133468409600491925317437998458582723897120786458219630275616949619564099733542766297770682044561605344090394777570973725211713076201846942438883897078408067779325471589907041186423781580046903588316958615443196819133852367565049467076710376395085898875495653237178198379421129086523
s = p - (pow(2, p, p*p)-2)//p
q = gmpy2.next_prime(s)
n = p*q
e = 0x10001
phi = (p-1)*(q-1)
d = gmpy2.invert(e, phi)
m = gmpy2.powmod(c,d,n)
print(long_to_bytes(m))

复制代码

		自动登录	找回密码
密码			立即注册