# PoliCTF 2012 Crypto 100

Since I needed to sign a document I thought about doing it with a Chinese paintbrush… Too bad my hand is not that steady, so just in case, I re-signed it with a common pen.

Sadly I keep being forgetful, so I actually forgot where I left the two halves of the sigil I used to sign the documents, can you help me and retrieve them from the two signatures?

Please, once you got them, write them as

sha1(part1=______\npart2=_______)

replace _____ with actual numbers, in decimal.
sha1 hex-encoded with lowercase letters
smallest one is part1, biggest one is part2

Summary: RSA-CRT fault attack

The description is very unclear, but when you know the trick you can see some logic there.

First, “Chinese signature” corresponds to CRT (Chinese Remainder Theorem) and with RSA it’s RSA-CRT.
“Too bad my hand is not that steady” means that he made some error while signing the document.

What numbers we are given:

• mod.txt – obviously it’s modulus (4096 bits)
• chinese.txt – looks like it’s RSA-CRT signature with error
• steady.txt – and the right signature

So, here’s the trick:

When signing in RSA-CRT, signing is done separately by p and q. If one of two has an error and we also have a signature without error, we can quickly factorize modulus.

$RSA:$
$rsasign \equiv h^d \mod{p}$
$rsasign \equiv h^d \mod{q}$

$RSA-CRT:$
$crtsign \equiv h^d \mod{p}$
$crtsign \neq h^d \mod{q}$

We can subtract to signs:

$Diff:$
$crtsign-rsasign \equiv 0 \mod{p}$
$crtsign-rsasign \neq 0 \mod{q}$

Which means that p divides diff and q does not.
$gcd(crtsign-rsasign, n) = p$
$q = n / p$

p and q are the answers.