Tags: rsa crypto z3 factoring
Rating: 5.0
**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}
