## My Sieve### Challenge> We have captured one of the most brilliant spies who successfully broke a private key! All the [information](https://cr.yp.toc.tf/tasks/recovered_54f706f7fb8fc9718a4600d0000987ea4bcb03d8.txz) gathered and we believe they are enough to reconstruct the way he used to break the key. Now, can you help us to find the secret message?
We are given the encrypted flag:
```enc = 17774316754182701043637765672766475504513144507864625935518462040899856505354546178499264702656639970102754546327338873353871389580967004810214134215521924626871944954513679198245322915573598165643628084858678915415521536126034275104881281802618561405075363713125886815998055449593678564456363170087233864817```
A corrupted pem file:
```-----BEGIN PUBLIC KEY-----MIGfMA0GCSqGSIb3DQEBAQUAA4GNADCB*QKBgQCkRgRCyTcSwlBKmERQV/BHkurS5QnYz7Rm18OjxuuWT3A*Ueqzq7fHISey2NEEtral/*E7v2Dy59DYHoRAAouWQd03ZYWnvU5mWoYRcpNmHIj8q*+FOtBWcCGzMZ8uxOxaV74vqqerjxyRI14rXZ+QOcNM/TMM84h0rl/IKqqWsQIDAQAB-----END PUBLIC KEY-----```
and a `msieve.dat` file, which is a file outputted while using msieve https://github.com/radii/msieve.
### Solution
#### Msieve
Looking at the data file, we see that a `~350` bit number
```0x1dabd3bb8e99101030cd7094eb15dd525cb0f02065694604071c2a8b10228f30cc12d08fc9caa8d97c65ff481```
 was factored. We can recover the factors using the command:
```./msieve 17012713766362055606937340593828012836774345940104644978558327325254454345526470012917476548051189037528193```
where we must ensure the data file is in the correct directory. Looking into the log file we find:
```Fri Jul 30 19:34:05 2021  Msieve v. 1.46Fri Jul 30 19:34:05 2021  random seeds: 98cfb443 69ab82ccFri Jul 30 19:34:05 2021  factoring 17012713766362055606937340593828012836774345940104644978558327325254454345526470012917476548051189037528193 (107 digits)Fri Jul 30 19:34:06 2021  no P-1/P+1/ECM available, skippingFri Jul 30 19:34:06 2021  commencing quadratic sieve (106-digit input)Fri Jul 30 19:34:06 2021  using multiplier of 11Fri Jul 30 19:34:06 2021  using generic 32kb sieve coreFri Jul 30 19:34:06 2021  sieve interval: 39 blocks of size 32768Fri Jul 30 19:34:06 2021  processing polynomials in batches of 6Fri Jul 30 19:34:06 2021  using a sieve bound of 4223251 (149333 primes)Fri Jul 30 19:34:06 2021  using large prime bound of 633487650 (29 bits)Fri Jul 30 19:34:06 2021  using double large prime bound of 6968329308179250 (45-53 bits)Fri Jul 30 19:34:06 2021  using trial factoring cutoff of 53 bitsFri Jul 30 19:34:06 2021  polynomial 'A' values have 14 factorsFri Jul 30 19:34:06 2021  restarting with 35905 full and 2217078 partial relationsFri Jul 30 19:34:06 2021  149536 relations (35905 full + 113631 combined from 2217078 partial), need 149429Fri Jul 30 19:34:07 2021  begin with 2252983 relationsFri Jul 30 19:34:07 2021  reduce to 393304 relations in 11 passesFri Jul 30 19:34:07 2021  attempting to read 393304 relationsFri Jul 30 19:34:08 2021  recovered 393304 relationsFri Jul 30 19:34:08 2021  recovered 385553 polynomialsFri Jul 30 19:34:08 2021  attempting to build 149536 cyclesFri Jul 30 19:34:08 2021  found 149535 cycles in 5 passesFri Jul 30 19:34:08 2021  distribution of cycle lengths:Fri Jul 30 19:34:08 2021     length 1 : 35905Fri Jul 30 19:34:08 2021     length 2 : 25563Fri Jul 30 19:34:08 2021     length 3 : 24612Fri Jul 30 19:34:08 2021     length 4 : 20585Fri Jul 30 19:34:08 2021     length 5 : 15651Fri Jul 30 19:34:08 2021     length 6 : 10638Fri Jul 30 19:34:08 2021     length 7 : 6982Fri Jul 30 19:34:08 2021     length 9+: 9599Fri Jul 30 19:34:08 2021  largest cycle: 19 relationsFri Jul 30 19:34:08 2021  matrix is 149333 x 149535 (43.3 MB) with weight 10166647 (67.99/col)Fri Jul 30 19:34:08 2021  sparse part has weight 10166647 (67.99/col)Fri Jul 30 19:34:09 2021  filtering completed in 3 passesFri Jul 30 19:34:09 2021  matrix is 143467 x 143531 (41.8 MB) with weight 9815366 (68.38/col)Fri Jul 30 19:34:09 2021  sparse part has weight 9815366 (68.38/col)Fri Jul 30 19:34:09 2021  saving the first 48 matrix rows for laterFri Jul 30 19:34:09 2021  matrix is 143419 x 143531 (24.4 MB) with weight 7565741 (52.71/col)Fri Jul 30 19:34:09 2021  sparse part has weight 4961307 (34.57/col)Fri Jul 30 19:34:09 2021  matrix includes 64 packed rowsFri Jul 30 19:34:09 2021  using block size 57412 for processor cache size 65536 kBFri Jul 30 19:34:09 2021  commencing Lanczos iterationFri Jul 30 19:34:09 2021  memory use: 24.2 MBFri Jul 30 19:34:10 2021  linear algebra at 4.2%, ETA 0h 0mFri Jul 30 19:34:34 2021  lanczos halted after 2270 iterations (dim = 143416)Fri Jul 30 19:34:34 2021  recovered 16 nontrivial dependenciesFri Jul 30 19:34:35 2021  p2 factor: 11Fri Jul 30 19:34:35 2021  prp53 factor: 37517726695590864161261967849116722975727713562769161Fri Jul 30 19:34:35 2021  prp53 factor: 41223455646589331474862018682296591762663841134030283Fri Jul 30 19:34:35 2021  elapsed time 00:00:30```
and so we have the three factors of the number:
```Fri Jul 30 19:34:35 2021  p2 factor: 11Fri Jul 30 19:34:35 2021  prp53 factor: 37517726695590864161261967849116722975727713562769161Fri Jul 30 19:34:35 2021  prp53 factor: 41223455646589331474862018682296591762663841134030283```
Now the question was, how does this 350 bit integer relate to the corrupted public key?
#### Corrupted Key
Looking at the corrupted key, we see 4 `*` though the file. This means naively we have `64**4` different `N` which are valid. The assumption was that one of these `N` would share factors the factored number from msieve.
Looking into the pem format, we actually find the first character must be `i` and so only three chr remain to be searched through. To try and find the correct `N` we looked for `gcd(X,N)!=0` for all possible keys:
```pythonfrom math import gcd
corrupt_N = 0xa4460442c93712c2504a98445057f04792ead2e509d8cfb466d7c3a3c6eb964f700051eab3abb7c72127b2d8d104b6b6a5fc013bbf60f2e7d0d81e8440028b9641dd376585a7bd4e665a86117293661c88fca80f853ad0567021b3319f2ec4ec5a57be2faaa7ab8f1c91235e2b5d9f9039c34cfd330cf38874ae5fc82aaa96b1X = 0x1dabd3bb8e99101030cd7094eb15dd525cb0f02065694604071c2a8b10228f30cc12d08fc9caa8d97c65ff481offsets = [356, 620, 752]
for a in range(64):    for b in range(64):        for c in range(64):            N = corrupt_N | (a<<offsets[0]) | (b<<offsets[1]) | (c<<offsets[2])            if gcd(N, X) > 2**32:                print("w00t")                print(a, b, c)                print(N)                print(gcd(N, X))```
However, running this script we found no values of `N` which had `X`, or a factor of `X` as a common divisor. The rest of the CTF we tried guessing other things, but nothing worked out.
During the CTF, this was solved once, by HXP, who solved it by using `X//11` as the public key:
```pythonfrom Crypto.Util.number import *                                                                                  p = 37517726695590864161261967849116722975727713562769161q = 41223455646589331474862018682296591762663841134030283N = p*qphi = (p-1)*(q-1)e = 0x10001d = pow(e,-1,phi)enc = 17774316754182701043637765672766475504513144507864625935518462040899856505354546178499264702656639970102754546327338873353871389580967004810214134215521924626871944954513679198245322915573598165643628084858678915415521536126034275104881281802618561405075363713125886815998055449593678564456363170087233864817                            flag = long_to_bytes(pow(enc,d,N))print(flag)           # b'CCTF{l34Rn_WorK_bY__Msieve__A5aP}'```
This was an unintended solution, and worked as the flag was small enough. Seeing this, it's dissapointing that we didnt try this guess, but we were so sure the .pem was needed for the solve, I guess this didnt occur to any of us.
### True Solution
After the CTF ended, the real pem was released. 
```$ cat pubkey.pem -----BEGIN PUBLIC KEY-----MIGfMA0GCSqGSIb3DQEBAQUAA4GNADCBiQKBgQCkRgRCyTcSwlBKmERQV/BHkurT5QnYz7Rm18OjxuuWT3AhUeqzq7fHISey2NEEtral/jE7v2Dy59DYHoRAAouWQd02ZYWnvU5mWoYRcpNmHIj8qk+FOtBWcCGzMZ8uxOxaV74vqqerjxyRI14rXZ+QOcNL/TMM84h0rl/IKqqWsQIDAQAB-----END PUBLIC KEY-----
$ cat pubkey_corrupted.pem -----BEGIN PUBLIC KEY-----MIGfMA0GCSqGSIb3DQEBAQUAA4GNADCB*QKBgQCkRgRCyTcSwlBKmERQV/BHkurS5QnYz7Rm18OjxuuWT3A*Ueqzq7fHISey2NEEtral/*E7v2Dy59DYHoRAAouWQd03ZYWnvU5mWoYRcpNmHIj8q*+FOtBWcCGzMZ8uxOxaV74vqqerjxyRI14rXZ+QOcNM/TMM84h0rl/IKqqWsQIDAQAB-----END PUBLIC KEY-----```
It turns out that `N` was corrupted not only in the four `*` throughout the file, but additionally the chracaters at the end of the first three lines were also modified... Using the correct pem we find:
```pythonx = 17012713766362055606937340593828012836774345940104644978558327325254454345526470012917476548051189037528193n = 115356776450250827754686976763822189563265178727141719602571509315861796708491086355344129261506721466097001689191320289269213116060519988849918021824941560396659801251826221296538423055226122464968459205865316769204109964482429845998764457962631301677585992875791654646257335269595789163018282966936558671537print(gcd(x, n))# 1546610342396550509721576417620728439706758721827694998050757029568586758684224546628861504368289912502563```
and so our idea was right, but we didnt not understand all the changes. Essentially after factoring `X` with msieve, the challenge was to replace all `*` and also know to modify the end of each line. If you have any intuition on why this is the case, I would love to know.
##### Flag
`CCTF{l34Rn_WorK_bY__Msieve__A5aP}`