**Hard Copy** was the best crypto challenge in my career and also one of the
hardest. I was given 2 files: `printer.go` which is a golang source code and
`capture.pcap` which contains traffic.

I started by analysing the pcap file, however all packets were encrypted
(https)

I looked at the source code. It is a simple web server with printing feature.
These functions didn't contain anything important. My goal was to decrypt
https, so I looked how the TLS was initialized.

The most intersting part of program:

```  
const bits = 2048

var bigOne = big.NewInt(1)  
var bigTwo = big.NewInt(2)

p, err := rand.Prime(rand.Reader, bits/2)  
if err != nil {  
return fmt.Errorf("failed to get prime: %w", err)  
}

q := new(big.Int)  
q.Xor(p, new(big.Int).Lsh(bigOne, bits/2-3)) // ensure q is not close to p  
for {  
if q.ProbablyPrime(20) {  
break  
}  
switch q.Cmp(p) {  
case -1:  
q.Sub(q, bigTwo)  
case 1:  
q.Add(q, bigTwo)  
case 0: // should never happen  
return fmt.Errorf("failed to get prime: p == q")  
}  
}  
```

The program safely generates a 1024 bit prime. Then, the second prime is the
first one xored with 2^1021. Basically, it checks the third bit of prime. If
it's 0 - 2^1021 is added to the number, if it's 1 it's subtracted. Then, the
loop checks if the number is prime. Until it's prime if the second number is
greater than the first one 2 is added otherwise subtracted. These primes are
then multiplied together to make a 2048 bit modulus.

Since the primes have something in common - they are not random the RSA can be
broken. A set of equations can be written:

{  
y = x + r + 2 * i  
x * y = mod  
}

where r is 2^1021 and i is some integer

The difference between x and y is a constant = r + 2i

As there is too many combinations for human to solve it in real time I used Z3
solver to do it for me

```  
i = 0  
while True:  
s = z3.Solver()  
x = z3.Int("x")  
y = z3.Int("y")  
s.add(x > 0)  
s.add(y > 0)  
s.add(y == x + r + 2 * i)  
s.add(x * y == mod)  
c = s.check()  
if c == z3.sat:  
print "ok %d" % i  
break  
i += 1  
```

After a couple of minutes running the script found `i = 579`

Then I could calculate the primes for private key

`  
x =
142868719742863293783230979998595876793415956014235960922151036241155398557013175374929194646682931157376392447724131367775640007550829960268051112176549732008858300548786079341071746721635835744957674944791270662022918676753662719533721899116906331154776508780823125564615147531881573980598054432598254739019  
y =
165339883928642242629847294883458685963640668251014793081329796385871983032700795766517754311983873160016406682708055537482988728652632038079657041006483997556079287226894265000609524171791597509889310313801896383127687512046470579717961037934509735800195322616396412844608553274191538518702473973801282757329`

Having the primes I can calculate phi

phi = (x - 1) * (y - 1)

and the private exponent `d`

d = inversemod(e, phi)

With that, I could construct the private key

```  
\-----BEGIN RSA PRIVATE KEY-----  
MIIEpAIBAAKCAQEAux8Y1h0joy+G2+MiW9elbKZawWmSdQvQ8ou6+Xf3TunKB+U9  
wZ2gkZftrkODEmhhp1pxe4QSr09dgT3BjSPqg479+yUavh6VFYgnJtLBjMtouYEF  
HZNg09tWeaYIpgh6Gcdn5mUEZQb4eMQEQxgw/ptJLERD9Ys1wmeICNLcIfu+aTbb  
9Q/cS1AGazGFVzTpCCsWK5FbEx5+pxBhAeN3rjst125IHUtA0MYVisfP5zNi1sh6  
SPN7V3gc1x4Z3rYHjbQtK1ms/secf7MNpnA58rLpjdEe5Oy1WBBQ8fmKUZZvQusc  
oBUyc4aY00kt1G+oUenP7TNDojLEVlKqcGOxOwIDAQABAoIBAEp3cKndBM6vXkrp  
lEXahvG7LkjkW62K20d7Bhi7fkcAUS9dMnt34Guwe50rLuFHev1fx+OwxsLPodWK  
HxmtHmnmoPquZHserpPYEESqAO6oEHAqgT+o5BLLqhlVUwHIQ9c4fQe6UcpmwMFG  
uK9+1Biu8arVK/puwSExlHh2ebZny08Me5LCDu/oFU3eRGwTZTgDGQ0ASnboR9nv  
S9CGqa7+r8R4z1ZPJOFS06VZI1IgZjNRPTqsRZZsohykbUvbAoyVm/MD+1w4Gghr  
xoQCy3PU8XKgYXiO1e1/rRG53CjBLkF/oYi8w5jhM5/ZK3wjoIo2O844ah4etrDj  
4k4nrCECgYEA63Op1ffzh7O91iBtN5T6tcrc2md98dkNX6/rnNbMe4zKTPbsBK5f  
mzQFsPKn5S/rHxceJyfxYbSOxkJ1VYKMYpZfO97359I03cjvWhY0PRjqFRZJr1pa  
kFyOnm3mqoHN//4g68PTD3S7HqCvTTQOIPy+V1umf6fttcKN1qhE4tECgYEAy3Op  
1ffzh7O91iBtN5T6tcrc2md98dkNX6/rnNbMe4zKTPbsBK5fmzQFsPKn5S/rHxce  
JyfxYbSOxkJ1VYKMYpZfO97359I03cjvWhY0PRjqFRZJr1pakFyOnm3mqoHN//4g  
68PTD3S7HqCvTTQOIPy+V1umf6fttcKN1qhE3ksCgYEAtsa8EdEAqNh8Rsw3XI13  
LkaDubvbRjJDsoNDOSZ56HM73BFW2K9wom/49wr4EO9o62Kr0qOsOzfKGdgfc7j7  
N9EZrsWA1uIUjhLc06cm+ELt/F6n5ssSQLzJLe2MwdIwU0g40CzdHEN2uujsDNeb  
HDp3nCMWlkSLQKz+JKPNjfECgYBtOXtEVAl6IRUZj+8Sl/jBAFfxKP6EiHKVnGxx  
lx/QdJVnHGk5WiQZvqQPizZ35HHmDxMxElCUk8rSxXsYnS2g//nAusN8wW2AZA+b  
3a/N3UJOb9i/O1LDje1DQN1FTMq7VEN4T3lQIusSVlHGsNuk+gt1+s44Wn9TxU9A  
nrXaYQKBgQCdSXuKyPIFXggFQ2t1aPhoT51u0tBBRDJNgKkEVKxwD03c7U5Fyg2c  
nGJkzgAVcpXOBo9DFyKIvJn7EAbJZGe+MAJCXKsdmc5EMqNMAC08IN088QYw6/gB  
KA2eCGtHX/1ReRVJcH/PNI8NjUHZV6pGE5dSHaN910JXZ+1/u/VLcw==  
\-----END RSA PRIVATE KEY-----  
```

After inputting it to wireshark the traffic is decrypted.  
It contains a few packets with a document sent to print

I extracted the pdf and there was flag a picture of green Square CTF flag and
a flag!

> flag{f3rMat_For_NAu9hT_2563076}

Original writeup (https://github.com/mar232320/ctf-
writeups/square/2022/hardcopy.md).