Writeup for Share in CNSS Summer Camp 2019

TL;DR

Solve a modified RSA problem, which used the product of 3 primes chosen from 6 randomly-generated primes, by recovering every prime (actually only 3 are needed if we want to calculate the m, e.g. flag) through writing congruences as equations.

File

Share.py

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
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')

cipherlist.txt

0x8f83bbd164fea268a30bcb4715045d83aa8ff882795f19149a19edeeb5543c845b09669c1448047722dfba93160e1b1b9513439808d2dcc898980b5fcaca8e103033b64faf3670448ad03e8c4929c5b381f2b5f8068c97612d04d819ad2bdbeb7fe1aa39cf569a19c3e6e400a8f7d239187df89f1325d8b38e487a183cca7a95295b5bf9f59ade348c338da8430ec1bcf45870898e458d7a07de5a55748f2eb94b357f878c6ef14198839615ec71a7bfdd6de265144a016f26d816d7d5838f750a26416559095acf7def0407fb01ee0198dad1088ad0eccad9342f21a4e02c5bbe2b53813db060bc7d6c134835af8cae696ceab3483820704a28548ba109127d42b197f97a242a84eca20ff2e495eabd52be86d6fcf1cefbdcdebc2b533e9dc7b2f10eef53dbef2237edfc2a47de4e2e1fee555440ae39136cfdb24a643772e536901091607abf030aa83894fb95c8076885e41282098ac82c5c7666bbc387ab6b64c87c10dad611ce3c4d8c884e52254b031fc4fd4931d0e9540a5cab1aa9f4
0x2dc31a1689ba766d73a11c19da4829ca8b42c250499a4c27d52574d0f7c53c3c355fc90654dba3acaddc4a0fda44ba8500e23e1e75e93597c359364cabb0bb522dddf68d80b26c1eae56002e2f66d71d3eb84da0fec44a459786563698a9a91d4f5f784983cc45b7c8f010c7160a416a863e0567b4076803a8e8439991a709a6014ed13f741663772e37122d24e4bca831c3119628cf83a5816969c150656f32d9236fc281fac8780116f3c250f597b1ef4d8dffee83b559c9a53cfd74853b5cfc5db7413e4daac9a5a7b264d18e9856e9c3e81edf989693a65db450b395a68ef7690c56ba93a134fc80c0065dd142256fe3aaf21ea534732f6d1c240d343fb6878e5ed347be733e1b58fba8857578ad7e3389c53c159becf4ca78f7a9c13db52c7328efd969e256ea70564e1d56f691925f37e9f9d87fe899e756fb77581065ec123601dceea2f5ea883beeaaadfdec3219ce0e10ea05edc0cadbdcd08b1c16484bdbced1c9d4059e99363023fceb2418231c1c7c5f8494247d23733ab0790d
0x281a805bc3f0922ca02aeb516ff0e42a87a50745d89b5725d977d533c2c119b7b590c58c95cdf467922088609866c83003766808adebbb10fa1c49d666692484675be1e74c986da24dd5ad8d7c6a62c5671c414044a7c3707bc074621d5d10d0ac0268bd90396c514e5e2742ba27255f5145bfada7398cf1233194f0a92f725c9a655bb9785b22f16fc9217dd00ebcec1f58eba97aec22decf7262499e9009e02ef8a95f711f1f78fb8515d0086653ef6bf96b5fb72365740b2a9670181ed79a6edbf324ad0a1e501af37e186e76e690a56f17dc0f8740f2d471162e366d6b6324c7d9762f85e935db406775463c6483462ec1ac14c2f3d9055ac9c41f6abfbb2716efd132b6db0b99498ac84bbb3edf7a449d95ce2051a34bbef683bce66209185d182c726964ab07751392f373c71e4af73b1608cee4fc97c63d640f84bfc5dbf22fddddef5eba956976e5d2228ad423feb38d189602f1581af8ec5be3594afbbe55cfc4e0b2f6946adc56d9480d90fdfb0646217fe7a53426bdb6d447ebd2
0x48f2c2cee8f3c8b0e96a83569156b904e7836bcc3b5bde9ea4fe7bfb5bf1c992069be704497dfff6fd91f693932f119dcf724b564686ee4725b8cb4aadf42dcd9daaa5cb31d294e003f7d2d1953e97b4cc7a71590b3a726b15970d4e56916eb81b9e6578bf4b2558bedccb75fabb92cb52302694b4a95194d1f3f0fd31d779006c0d388d26555f1337b0e5287962587d461a523ae9d0a31428aaeef4254362d515a4d39cee8202b3290fbab1ee8f21a8ea5971087a742d67ba7d4896a203f7a93c7c641a7aedcc1bc62a8397d40738714ce33c614ab7acc567c14136a4175f071a707ca42671a7edd63d54cf6a7809cf72bda56ca4f1d61ffbcc2b1f2e4c72939b60a860dee236c7ed28ea6af538f1c823c4c98e3a4f03ef45d21ac8f4cadb91523449e31b688d99613e712dcd00ad7dcbee8370e587de3afd8d9526c7e2cbf61af1735b7401eb7be6d61cceec4839bf81d84da7839794c4e14e30745cc0be00d1ace1003239d4e075ea985ff8bbcc2735bfbd5f09b93f78ee5cf77517815efb
0x372a2aa70f441f13d1e3a93b8046d86649dbee1184e72b4c7949ee39af24196adc75286f25c0df068a2950259994b11c8ce40a1628e2fa6ea6577e4858342be639f54e3530aefdc027a93fed9ca2a5289b5b0d4e2ba560531ede93a4257853cc907251a47fa2ad07cc58005061ef6c726e0e2e47d5d73b3df6fc61fd734c6b1d264e767198554379f6da9e91407bbf03d535d620bf318ee97e1b4710335f5df646b0cfd277cf62ff9a950004b188d7609ed3f513808774f4be732c4f2d478ad4599bfe0929418c4dbbe7ba69cc7da0032ab8f6beae730fb200a3ebe9d1f6bbe4ea4ce3e130fd13bef0733ef3070fb54bc2b6afb0531b05adab315480a3640969f0d147b7d5bd70ba1ddc3fced7d5d85fa5eaab0d9e7fe4aa649f9a7557cc9c1e532dfbdc22d4c621b9d9147990b13602469afe243372e62e58e513bfa0e7588a9612a62def541979d13375e06ccf28e0b8b7f5c22e8bec26bf26c0ed221d1c5fc1b420a98d180e49f1310bd44c5c2cd19a0f1bf0ffed6a678e136f19041cc93b
0x38cf70f149fbe50b1a8892ebed5834696bd79781e3238a8331481c870fb4536e25f6bf4c7571b478a01389c8bd8c77614958c1a2953a39960174b4b60ded7de06d179a4a93e1ab48438b4a4c8273e4fc716119d4f4e9e5687a5d6001a8de1486b6db5a5344172504b63180b92ef0a487cfb57487b9e7201c5c39c17a23ccd8f0168a184ec31d184b24a5de4a4f13050b4312c251e99dcd57982f4eba5d6095bd1fd7d7cc62bccb6935212153623673e227b06e2c9b083cb2351a5cbf886d7d70c5823705a5027b03436c228d9bebd85f31465bc82e7ea85eeafaf45b847a57d9951f4d8fab0f8e3009d58778bca9b747feeba09f858f988c27e6dde7c643c01b2ec79c94cddcf94b73d6523a45f1170c817f30f1c3ba8bcdd9abdb3e4d68be20450dbfc9d3b2e271a77371c22f8a02dc30f530f31a755d496e5e9f7a64e5418fb8a803d66b15120679271596b74bdb176123cdbe1c6b0eee9bc072a04cced59b6e8a920430d9a91ac0bdee6b2b00dd4965c7b3941c728f4e03acff0067bdb476
0xd3bce59b15f87b90f043e1f1043f025e5bf9ef1460a8366c485826083ad4ca93c4344d499fc9daf318a99d442e478117f379e3908812d2472a7ff5aea596cd6e2dbafac85cb6f0d3f4e8d1324b283c56f30a78f476f00ac26de02459b4c7e3d17d125339eddc47e4300e930a5af18df8811c2c4904405bfaac84a2c6df7feb5254a7b8fe642f130ce9af57ebb50ca773a2dc76c53d9fa7b48e89ede8a84f29e859452ccd41d7cff1de6a756cce5a34f514e02c7ad11bfb2689c1581b6098d3fef1551be7c430dd6bc1baf624a8966504850921062861a60e5e90a6ea3ce8af257d923556a969a5d2badc4e01cf7a23b739b43ce68d4a3f98236ab54ab06e35ac78ac8d295357e23080e411a50b7e47bc1418a4b1cc9c30848dd9a8a02241455b4e58f6b4e47f59f062aa6ef0942a4d83062a3660c24171d6d7d70a6e57552fbb46b76394e61651a84d84fa06782773c872cea4d51fcc2b66fe56dea77c4c88b1bf036dcc937cb83371126566c817fd856154fa85b908434093308aaf8c01214c
0x4fa377d624afca3fc0003df5d117d79e9f951d2f47d3b90c7e254fd120f7cae34915b251f629b182bfee2977213e68a8c9f6be698d15ab8fa82c7e26b5d7890d2eeb4cfde4eab5e85ef6e9f6a8b9bcda7036f1a8af6846a620c64cc1555ff1824579bbfd4e51f0aebb825e652195a10f792acf69c347fae73a53cafd986d2262b8e7e1acd6b42a1f995558e44c2a025b96a0f61f594e44ebed1918d9e788370c69b7c73eff8ddb4f4c386258093dc8263567fa69702f745d9ae33bee7b76976a7a8b5548be810b50d08f24b5ce251cd7c9af42a8cf46ebb48106ba8dea9e0a12377ac075613b70ea321a677ae5a44548cf5485ee85290445c748bef9e1e339f9a4457225028d4ea08dca676eda38cd0525b1dbfb7a41bd38eee6cb9be654e867d75a9b7150c3c0b31a3c5355db45a7daf9eff8849b1acf8c2697452301e65673c719972a9d9e240050508bee598f4829d8af04b57de2199ee6fedf91f7771a746321edd09b044c636b7de0bdb15d74346e1f32ec3626173e4afbdfbf84055393
0x5b62ebe08e5b82148b5776aacce6c61dc0ff4a3242cc4fa86b1b8005427076f4613544d8c3059da6d892119ff5466089c13aafd5adede63f39721620d7823b469c12aed78aa5c26b19514e8d5be356812d18c42207d65f53e34eeb2cd6ce559fddd9a0c6a5f36c25cc8a3be399b82a2e20f81ef1d6a495ca9e983738244ada51f97901aace2b4dd432eb142c90e78927ed1e6e2c81b09683c37b8c3716d090493ac19179b89abcd0e60d17768a4db9a52cb30fd74d8b6c939cb7e8128029d30e1b39f8dc14a984beba7520a0e172286210c0ce73b7da94130e61b5bdd2b3927fa0ac56d5067abc26454b4b446947eec81972c04b4d155e6eabee682182ced590b55de99dd1c8cfab12512670fc8ac583ced1a9d6d880859593dd7af6ac0ee6eb13673287ddb90583019489c20f83857dd394845e2d2cdbae71f892c94d0660576a5d94614cbfd741b2ae30536aa27a59d29c3d1e948488e04b68832d096a6ed319703e6b70020e2bdedfc9e44f953036eacb403a5d4e927c0d3f2779290752de
0x1229940cb26d30cfde2f3bd76875ae8723101849bdaf8472a4a608e934f55a60a113ad1aea82a2c86f22b4d31b64defb2a6be8466558081d46d3a1b686fe4c3f8c70893c6fa69eccb055a08167f5e11dd7cc2da26183a6a118653c6dd762d48e7b658549f3f78be2904dfbefdecefb4c8496174fc0087d0705b22925ef6563ff8fe42b3017dbc577fb4ab27c80208a5905cdcb28dad026b8e0dcba325edac48843e8f694920f6637e02d758a07f31e128c289d98625cb0695ab81eb6355637e78ae6c43bb58cc05ff6be458dc8f6e7766b6097780b05b63a580619e857eaa3e70ab8b0eeeddf0699d2c04cc18f5b2b19ec617014da47b7b6d8dd544ea02e85022ee59b88d5b81f7e50b67b469c4f98ca472988077653fc80e73363a8b7a53aca1c0f0d54acccd1b2f42f2fe3f295d3c50505791614aa57b3626ed18df7871bea968a4742515b3827d8d1602b22206b36496f7fada7ca6dd1aef935a1349bd22e186302c068ce527314d2ea2c7f7bcd9e06e1963b539d864ef0394e446bbaef7
0x3dbc94af875b11e51cfed96cd640b3f39be138895d3fb1862355936e11f031c13d73520b335d9c97ddc39218bc04166f82ae490445b7a9591deab89a8323e04f4da83c17d915ce7534b5d4745d71e9675919bf45c29fc49e0cdc56f5ad5e15744398029c0c6b6754c07d3610342805d572a50dcd9d00b2a7e2521f96b095d27a0501c9fede3af638e9a3e21feabfc035834ec6b4065d88b156245782cd212c1d79d96fbabb3eff27f3c3122f6421e60369e509a0ff0a55252c7b67f6ac73df2440a692ac57daedbeba56063acde55e8a01bbe3f66f7bb85ae9ebf77bd1ce99a549d3933d6797f258f11d774b28568e48cc3ac6820e837c5563600c1adefd2c36811a2856ffad79f1f08786d263f80bfe7c486bd6f0c8dc0c6dcd045a5f0b2d4d32dd5366a21e4e9f406d907fe0ad82aee05d124e6ced6a8fad5350cfc70a500d43478d68be892d32f35e5dfb283547649a69170510e5e2669b532e9e8228f76de36b91bb558378d77c328062061e34d57f7c341295c2555e5682645f23d8091b
0x31d1cee7a2202eb4264dd96fe68057e30a88520cf0eb856de2ae0d5cfb1731cd2a092b01cca28b31a8ef7878a1d976c321404323d0898f726a69696a987c08f4e7a7e835418adff3aa1fe30bab4ada7b89925d8a6f7fa0b984669bda103f2994306e49990d4b9f9d9be7935f03ac2d85f4cfadaa30bde7f5193610998a164323f001b88a77cdb0aedce8718d686a25c04b7f91351c6abc2be2133319b91726e0c2a8b53cab2b17ccf0fb0a2fe579b727cfc3686198180fd8d78cd68eb0c9ddcf7fd70b55d47719dd488dbcad28a287f3377602daaa6cc07785cdc55599dc750f85011048ad0261fd54e54abc1a92e66d3be9b8d15077088b7893c6ca083ea94f75880e8c6e8ddcafd8b260e2e5d993f3e73d7c80c6e7d47413b02295072fc235d61003e157c476d0b8dc7c2d846dc180b1cac72eed1da20938ac4afcb5627c124af8b2f05a9dbc6443d51a75e2dc803c67a8002a6d46651a8440bac8030f3d46d643bdd3372592bfe52b0931ecadfcf577564e4005bd0cf6a6bbedf1a7121fe7
0x9c9aa94f29498ed403832d8b7cdec6e3aefa21f22a44f0af8b90dfd40adc319b6950773f4464d3225231d47eede9fb8d76a515640755af5016874ef14f3ab526f47b66b7e32ac02e412598582479b7d2f6ed85dd5c35e7bd9a8f2903594d35483d1ebd021a80229d0492c65805e9f831ac3caf8354e0d7bf27f18138e2de07cc4d8a3915620519d6d727cc62ee0f818615221b6dedff09d587d0dc7c17e99e8979df5cbd30af9778ae79c42ea0a982b4e03d83021197430848392e5ab82c3f3e9a068cbebb4dabdc4a72c606497cff319c980ef3af84ff36c8d82741531f7cd717f81e50acbf0b791d04f6eeff2dabc259703a30a7f1976957d472234a6cf2df2f0707052ad468dbed17d14ab02678c44ef501083c4f83c56ebe3cffa5d6c70dc206678f2057e0f04138318190b09d1cb2696cf17428269401e72344c56311f9cba297c3ceba4d498e12c1a5be1cf65328c9f56d294653a9da68ef41d4a4ef4bacd3e8d26e136f6b56c422ce542411d49e70569434cd902b9baa54927bab8b03
0x41f291d82527251c9e0e60c19533847f85e8bbdfd6d68c78a3d2b8dda39f18fb8ce2245d5d40974e0ef5d5f5febca0f6c47ba0ce84d775c1a7319f352861a395d6071e9ba5d170a71bf54b6f1a5bb2571192a5294a7724e81a7077b3784dfe1859f242fd80088ea5eb9a65436841504c36e95214251fe81315139948802f584b9e69ca3e83cf8554d97597c9bb99847dca10e99a198beaffec903f5fe6915d8fd3877c4abc70dd52748eec05efeb5b0da50a690f509c9e13d0ad6157cf579956d18d757cc741df5662bcefed4441bc35c3a8d3eea7e25fa7e45d51cb099de4acf9500791a4077d1b9a4a37618b1f474421de928a68ebb9d2de55f4a2c4c3be53d3e0aa26d8dc22e5caa2ddb54169cd9cbb17a241098e8d2b5c0d23f7903d032de7da15b1ce49b9ac9ac76cfdc184bd52b70f4c008f974eadcbc9fa68978bb4041fdc6f61f110b106a18519751e64b78cb405cbb2ae4f9ce15d4e3613738ae24a3907127adbf0603b075bd1708c34df3ed5993bf31ac8a66a0440aef3217895ea
0x7e746ae63e55c80c7b5eb5968b582ed37370315c579b490b1776106dde972c25df324a4c263e58cf96890139927afbf732e4152e29fc6d598503518e460ee8ad5132d671dc82fb37760c90a0ac5c7cb2caf40e346e9cb287d86a2a3412863c533c9ce21e9fe8e580901bdf3a0fe4e6a6c262cd943a1dcc6b31ea8838af4537f4a70176c0154e0fba9d8fa414e1bb132c61435c4e8986f33ae34f514bc47afc96c2bbae0dc25dea6ea779c99ed06e92da229f0e5c16d6aa6f2b7f767b979ac7d44714d2d95e1718af0266100548322ff8fb492626782f9c54fc34b072a23d5da6bdc4212c402e2c4c999ab86350ced9dbaffcc32c868f1c5bc11d9610a66f82f2886a460b6220106621fa99fb0698bb7b4caf619c995c339ad50bda99902374d9bf46765de62cd047803e9294f70aba9bb0a991e618744142e2d458dd15c4df8f616f37726517acd5be7180d617e21486a1147545e6e21740531f939fef688c5283e084c7395e2695bd3d265fd18f16a7c961a24e0a4d55e0715dda01127b937c
0x82acf185accdef510be2f071667b1e038b135a1fe8514e1688f95928936a7064e2153b7890461f61f8e715fbdeaced90a8dfa9592fa92425ef467493f4c6d5f3995e9167c5e42736474db4cb487b0085f0b94032d96fc8302d5236a8885f7962f370f28e041250f459e908c1de4a27f6df0016be0e1624dd05041e43c733e4fbeb855128685c70c85a05e1f148891da4786c6c132ee908c63a39384ee828a04a5e58cdfebe21b45fb79e184083259dcec2c7a8e05d419c5372110163d20320a32e59c73a48aefd8079551a32007417dd6f147c8b39fed33e67e99e5cdeb754945ab00cb30cbf72db81948bdcca2cf06ac32ee9c0ea48a403c842f85a72acbb48dae07e7ec3dd1894ceedfba82e93d0d95264cdbd4b07e1c910fe899861a503714a34dd01417f2931e2d8d6fa66a3e597bb28167c9045803c9a9c9f12d3de8029b3aad38d82d353120be772afa32af9e5b7a80df6864435665651fa5061abac02272371dbddd324878240fcd51f97093cc579f8e38a98a0a43be48ba25bb001
0x62a6e17d4482b50a3a433ef3aed20487916ff87f77f06e8685be99cbc3de63dabcbd1a58c7fa882d929c35b1ff150b2af3258cc4627768511397fdbd51a2ce2e33e7d3173c6d1cd67d7cb0907173403e63376a4545c2953938d217f35b8e511fe980d3725441e1b7f6724d14d397ea8685069c912d1c4705caeecb02ceffccdf73cc3b4707a339c8d36c06925b7e96269ec12d291663c0afbfcc8d3a2c2bb92732cc328535b802489f1c04a5ff52158ca1da022c6dcf08e2725f6700e2c3d33cc7c9ff9c04e847ec52579adc106cc2520584ae3216665cd3a79fc51a15da403df3f439973b612be7b6d80d40bf6c67748f5595fce1155f31551d4901bf3ba69961f89d28acf9a2b1d1c51f7610b31c6cf8d782950f699668f1db72621f626836831d2e8f91bcfb8f8ccbb0afce2317f396ea773237f3b09b3f1c729e2cc6d36d8b3980f1849f5d5ef6419bc8605d08b61f67be9102dba66c645399864c0684b3228f838e36a79f97c67b5025d1e800ff389e0eb4cc1657251807f15482501047
0x400e86bd60fc7d01cb8331e87b4c7bd6b303731c9b4e8d245d34e564769810a251a341a5aa70e7370f0f641b0c62f16f0d8fef61dface09e297916dc65a60608f4ca02ac4be88dc6331f6ed2a091707d2ebc31c3cb0e734d7b3264c4aa389f0ef03a95035b934be0c10388784641dceee4fab0f5e6cc21435e7674cfb3a85ecb90b8e1e214280312be8eced167dffa3f3ce3c6a2bd918622c6d5f4cd622673da5989bdb1db2d21af0f45ca6be3c580592da7a92619aee5efdde462a1a8a2417b5abeedff1c166ddeae0b570cba48bf44b3e7299ac4a358dc30d9dc69dc2ab7077271392ef643f0fb2c0015afa33f06eb09e12c719c26977a49d71794e885fae866d15f1e96cf12b8b9dc9d5afa1f19b896babb35fc09f765c0bb4d6109bf49c6a72a85ba6239c4dccde553198c4a3a7ba004092975a707a872416f23485af19f50bc591b4593190a620d1de9dd983190a1fc7b4f3cf558057d4f342fdca9d765977f116620f140f72203d3b797d0d09f30fef3ba8bb0e1fe528338f57c1ab408
0x6490a1865e1c53cf274ad5f4a35bd51aac436e85801c6554ac058dd25f06be6f7a35230c268f4663eb37802aa97164012e724739da25de0392ed9b7aa869dd7c7ffd6e9fa7a34ab366e52717b9fd16bf27c2db5f7d66d8e27b923508da55629459b311b23224775ab278ac59b1c5f2bcf34cfecc03619f22c5c0bd972ddb9b59cac34c9531925cdfa7bc4ff0e19075b4f4be9d7dcf1dcbf05cb74c2afbfe4509335ff114a11ef0f5e883321c6a4b401eff7d3c7e7488298a8302b734ab063451d4834d13c419208bc5a61ff84efb6bb4b0077b3fb7313b2d1e8b325c195b1bb91d959ec3e718b2870ba2ea9bc07b57b93ba5e069c099da0ef68530c95d3ffcb3380f5c064cb14d4e25aab0f6016dff1d3ae38f31b618db2156088e7a96fc0e283b02a7a8a7b87e6c8618275dc9f26f1ddd4ca75e3961179ffbbee62fa663e106fde1a0b9992bb504afa04d7f412b30847dcdca53378c6fa2256e89ac92144fd3b24de3aef6416c15505c7768df60eb3a315ab373a8e03d971323ce2fae32932d
0x77ad4fb838ded1c35055c6cd8ceab0cf3401c1e0cfb89bb429396f5f1c0c9073e13b7b741c54aac29a506593cb45f332961251afbf549794d36aed1b1765e6c7732bcda39fb6af3857498fa5e2f1275957218016e70912e153a4232a2cd2605781a46db2872698e26c0887f5bec99847e8629196613d702020d08eff123bf4d4b89171bf860cdc04e5629c137fa948a2f220c3e8e8b3d1340251780c5e4cd2c03dfdf1b47b6c57afd2f65a7d443118db1c9f03f2cdf0c07af7e65f133214d7e8bc9550492a6331eb2d1d848ecc78ced742e2dc860141f039b9812ed5c1e8cc0e07c4842b91e3732d4c23536359c0e657ec192b033060023021eec1612d6b757f0dae34f587ddcd01297446820d4dc5f2d73be005f26ae2d30e64d744d333c5ab7f395bab41203fd2fce0f3fe31f2b5d206289f5b63b7e071bf51a814bbcf014a6ff3a0fa6895873bcc1f660bc4974d4cc43da7ad4fe2dd2720323058efe36ad7cc48a6480b85f7ec5ef371c82a9b952d358adc07a2d528e2945212908a6e69b8

Recon

对同一个me = 0x10001 = 65537加密20次,每次加密用的模数不同,模数是从6个质数中取出的3个的乘积。

给出了20次加密后的结果,记为$c_0, c_1, c_2, …, c_{19}$。


先写出关系式,

$$ \begin{split} m^e &\equiv c_0 \quad &(mod\ p_0p_1p_2)\ m^e &\equiv c_1 \quad &(mod\ p_0p_1p_3)\ &…\ m^e &\equiv c_{19} \quad &(mod\ p_3p_4p_5)\ \end{split} $$

其中模数的质数组成依次是,

 1
 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
count = 0
for i in range(6):
    for j in range(i + 1, 6):
        for k in range(j + 1, 6):
            print(f"{count:2d}: {i:2d} {j:2d} {k:2d}")
            count += 1

# # output:
#  0:  0  1  2
#  1:  0  1  3
#  2:  0  1  4
#  3:  0  1  5
#  4:  0  2  3
#  5:  0  2  4
#  6:  0  2  5
#  7:  0  3  4
#  8:  0  3  5
#  9:  0  4  5
# 10:  1  2  3
# 11:  1  2  4
# 12:  1  2  5
# 13:  1  3  4
# 14:  1  3  5
# 15:  1  4  5
# 16:  2  3  4
# 17:  2  3  5
# 18:  2  4  5
# 19:  3  4  5

联想到CRT(中国剩余定理),但是CRT的前提是要知道模数,但这里没给,不行。

模数不同,对同一个很大的$m^e$取模,结果自然会相差很大。思索了一下能否对$c_0, c_1, c_2, …, c_{19}$进行一些线性运算来改变模数,未果,也行不通。


试着google了一下RSA unknown modulus,rsa unknown modulus share same prime,找到了一篇How to Determine an Unknown RSA Public Modulus

大致浏览了一下,里面主要是提出了在已知至少两对明-密文$(m_i, c_i)$时,可以恢复出未知的模数$N$。

但是我们这一题,只给了20个用同一个明文加密的密文,而明文正是我们想要求的。

不过,其中一个步骤给了我们提供了思路:

tips

Exploit

回到这一题,照上面那个思路,先从同余式写出等式,

$$ \begin{split} m^e &= c_0 &+\ k_0\cdot p_0p_1p_2\ m^e &= c_1 &+\ k_1\cdot p_0p_1p_3\ &…\ m^e &= c_{19} &+\ k_{19}\cdot p_3p_4p_5 \end{split} $$

左边都是$m^e$,试着减一下消去$m^e$,

$$ \begin{split} m^e - m^e &= c_0 + k_0\cdot p_0p_1p_2 - (c_1 + k_1\cdot p_0p_1p_3)\ c_1 - c_0 &= k_0\cdot p_0p_1p_2 - k_1\cdot p_0p_1p_3\ c_1 - c_0 &= p_0p_1(k_0p_2 - k_1p_3) \end{split} $$

这里,我们能看到,等式左边是可以算出来的,而等式右边中可以提出公因数了$p_0p_1$。

这是$c_1 - c_0$的结果。我们现在手上有20个$c$,再去找两个$c$,比如说$c_2, c_3$,这样相减后的等式右边也可以提出公因数$p_0p_1$。

$$ c_3 - c_2 = p_0p_1(k_2p_4 - k_3p_5) $$

再去对这两个作差的结果取最大公约数,即$GCD(c_1 - c_0,\ c_3 - c_2)$,那么必将得到$p_0p_1$的倍数,很可能就是$p_0p_1$,这个要取决于$GCD(k_0p_2 - k_1p_3,\ k_2p_4 - k_3p_5)$的情况,不过很大概率下应该是等于$1$的。

按照这个方法,我们就可以求出其中两个质数$p_0, p_1$的乘积,但是实际上如果我们选取得更加巧妙一点的话,我们可以直接求出其中的任何一个质数。


怎么巧妙地选取呢?

只要让等式 $$ c_i - c_j = k_j\cdot p_ap_bp_c - k_i\cdot p_ap_{b’}p_{c’} $$ 右边提出来的公因数是一个质数就可以了。

如果$GCD(c_i - c_j,\ c_{i’} - c{j’})$得到的结果是$p_x$的倍数,该怎么办?

结果必然是$t\cdot p_x$。一般来说,可以用PythonCrypto库中的isPrime函数来检验得到的结果是不是一个质数。如果不是个质数,实际上$t$不会太大,直接对这个结果factor,除去所有的小质因数(也就是$t$),就可以了。

Script

 1
 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
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
#  0:  0  1  2
#  1:  0  1  3
#  2:  0  1  4
#  3:  0  1  5
#  4:  0  2  3
#  5:  0  2  4
#  6:  0  2  5
#  7:  0  3  4
#  8:  0  3  5
#  9:  0  4  5
# 10:  1  2  3
# 11:  1  2  4
# 12:  1  2  5
# 13:  1  3  4
# 14:  1  3  5
# 15:  1  4  5
# 16:  2  3  4
# 17:  2  3  5
# 18:  2  4  5
# 19:  3  4  5


from Crypto.Util.number import *


with open('cipherlist.txt') as f:
    ciphers = f.read()

c = []
for cipher in ciphers.split('\n')[:-1]:
    c.append(int(cipher, 16))

p0 = GCD(c[3] - c[4], c[6] - c[7])
assert(isPrime(p0))
p1 = GCD(c[0] - c[15], c[2] - c[12])
assert(isPrime(p1))
p2 = GCD(c[0] - c[17], c[4] - c[11]) // 4     # factordb.com
assert(isPrime(p2))
p3 = GCD(c[1] - c[16], c[4] - c[19])
assert(isPrime(p3))
p4 = GCD(c[2] - c[16], c[5] - c[19])
assert(isPrime(p4))
p5 = GCD(c[3] - c[17], c[6] - c[14])
assert(isPrime(p5))

N_012 = p0 * p1 * p2
phi_012 = (p0 - 1) * (p1 - 1) * (p2 - 1)
e = 0x10001
assert(GCD(e, phi_012) == 1)
d = inverse(e, phi_012)
m = pow(c[0], d, N_012)
flag = bytes.fromhex(hex(m)[2:])
print(flag)

# b'cnss{Shar1ng_Prime_1z_Dan8erou5}'


# (p0, p1, p2, p3, p4, p5) =
# (177304879050333551776343860783076913000427102527188500840715464140010698844842835299190701847891781739300987077568541585369514970314051812200740938014996001750073210393068360124254486224833896088415593840580890258145758717471076717409517143322203320102372547426869957602303311721945479530782305397175250602643,
#  119645681381628146011902256693940867125453580799419325372785077552123523103473163699736651194110579933863386879119089895255069215489258925503404468239893965701321221532139408923594329309336302479215591228210351341183070466867074661162860746463288087453157590440658022835232240758264061900163591944740912499513,
#  179373542506561829194974889818444042734137695401667380750515018416052794964521133723808905996016609496683279256002175275511413703788693050396215119343308972004584336387459140250554225666319369063669244445902895494966205441352250626558617493456902583645316124764866501940305192122019244761649967689001185902717,
#  149290165591379682575125833004788457369492113232039504608217060477695761862559298411435879740793219106685159527303061598218721588225103172245461381649753544713326382994225730820238540297730801032547884791785723906376045268252778724253643174436033919863486394025860523829034378404781397173309380167911723074659,
#  112578603517527755751185035881323548618010735635726409237980550631674273604861886769505142567396678750653637599850432017841395087638059940264169744617948461842957920839103366365783819355538023530548578540764441439726473115616051358327778556162649360618615219156658953296355989175350497667452923301838076216447,
#  165662264644197770353023368706316773895872263104901495492709210410139622545700598428978201602479122247134397970490477811805425600864339810593429968361601617955051875019532938861969217445581419405017415570207316631518058784129821751924467921009903863228465259371932738347366806206771747428532807462024790065003)

Flag

cnss{Shar1ng_Prime_1z_Dan8erou5}

Summary

实际上,这一题第一眼看到,想了很久,也曾尝试着将同余式写成等式,但并没有发现这个解法。。

时隔十几天后,我先是看到了An Introduction to Mathematical Cryptography上对CRT的另一个角度阐释,又让我回想到了这一题,于是就又来尝试解一下这一题。

In addition to being a theorem and an algorithm, we would suggest to the reader that the Chinese remainder theorem is also a state of mind.

可是,CRT似乎真的解不了这一题,不过里面的将同余式写成等式这一思想倒是为这一题提供了一个极好的思路。

现在,终于解出了这道遗留在脑海深处的RshuSxueAti,心中顿时舒畅了许多。。