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
chinese.txt
mod.txt
steady.txt
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.
The flag: 33fe5ddad6a05457de0be72efac3b9f4b99383d1
Some slides on topic (Bellcore attack):
https://www.cosic.esat.kuleuven.be/ches2012/slides/S2_talk1_Zapalowicz.pdf
