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