**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 = 0while 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 = 142868719742863293783230979998595876793415956014235960922151036241155398557013175374929194646682931157376392447724131367775640007550829960268051112176549732008858300548786079341071746721635835744957674944791270662022918676753662719533721899116906331154776508780823125564615147531881573980598054432598254739019y = 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+U9wZ2gkZftrkODEmhhp1pxe4QSr09dgT3BjSPqg479+yUavh6VFYgnJtLBjMtouYEFHZNg09tWeaYIpgh6Gcdn5mUEZQb4eMQEQxgw/ptJLERD9Ys1wmeICNLcIfu+aTbb9Q/cS1AGazGFVzTpCCsWK5FbEx5+pxBhAeN3rjst125IHUtA0MYVisfP5zNi1sh6SPN7V3gc1x4Z3rYHjbQtK1ms/secf7MNpnA58rLpjdEe5Oy1WBBQ8fmKUZZvQuscoBUyc4aY00kt1G+oUenP7TNDojLEVlKqcGOxOwIDAQABAoIBAEp3cKndBM6vXkrplEXahvG7LkjkW62K20d7Bhi7fkcAUS9dMnt34Guwe50rLuFHev1fx+OwxsLPodWKHxmtHmnmoPquZHserpPYEESqAO6oEHAqgT+o5BLLqhlVUwHIQ9c4fQe6UcpmwMFGuK9+1Biu8arVK/puwSExlHh2ebZny08Me5LCDu/oFU3eRGwTZTgDGQ0ASnboR9nvS9CGqa7+r8R4z1ZPJOFS06VZI1IgZjNRPTqsRZZsohykbUvbAoyVm/MD+1w4GghrxoQCy3PU8XKgYXiO1e1/rRG53CjBLkF/oYi8w5jhM5/ZK3wjoIo2O844ah4etrDj4k4nrCECgYEA63Op1ffzh7O91iBtN5T6tcrc2md98dkNX6/rnNbMe4zKTPbsBK5fmzQFsPKn5S/rHxceJyfxYbSOxkJ1VYKMYpZfO97359I03cjvWhY0PRjqFRZJr1pakFyOnm3mqoHN//4g68PTD3S7HqCvTTQOIPy+V1umf6fttcKN1qhE4tECgYEAy3Op1ffzh7O91iBtN5T6tcrc2md98dkNX6/rnNbMe4zKTPbsBK5fmzQFsPKn5S/rHxceJyfxYbSOxkJ1VYKMYpZfO97359I03cjvWhY0PRjqFRZJr1pakFyOnm3mqoHN//4g68PTD3S7HqCvTTQOIPy+V1umf6fttcKN1qhE3ksCgYEAtsa8EdEAqNh8Rsw3XI13LkaDubvbRjJDsoNDOSZ56HM73BFW2K9wom/49wr4EO9o62Kr0qOsOzfKGdgfc7j7N9EZrsWA1uIUjhLc06cm+ELt/F6n5ssSQLzJLe2MwdIwU0g40CzdHEN2uujsDNebHDp3nCMWlkSLQKz+JKPNjfECgYBtOXtEVAl6IRUZj+8Sl/jBAFfxKP6EiHKVnGxxlx/QdJVnHGk5WiQZvqQPizZ35HHmDxMxElCUk8rSxXsYnS2g//nAusN8wW2AZA+b3a/N3UJOb9i/O1LDje1DQN1FTMq7VEN4T3lQIusSVlHGsNuk+gt1+s44Wn9TxU9AnrXaYQKBgQCdSXuKyPIFXggFQ2t1aPhoT51u0tBBRDJNgKkEVKxwD03c7U5Fyg2cnGJkzgAVcpXOBo9DFyKIvJn7EAbJZGe+MAJCXKsdmc5EMqNMAC08IN088QYw6/gBKA2eCGtHX/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}