# How to forge a textbook RSA signature?

Let $pk=(N,e)$ (resp. $sk=(N,d)$) denote the public (resp. private) key in a plain RSA signature scheme. Define the function $\textbf{Int}: \{0,1\}^* \to \mathbb{Z}_N^*$ as follows: on input string $x=(x_1\parallel \dots \parallel x_n)\in\{0,1\}^t$ we set $$\textbf{Int}(x_1\parallel \dots \parallel x_n)=\sum_{i=1}^{n}2^{n-i}x_i$$ We also let $\mu$ denote an ASCII character to byte mapping in which $\mu(0)=0^8$, $\mu(1)=0^71$, $\mu(2)=0^610$, $\dots$, $\mu(9)=0^41001$. Given an ASCII message $m=m_1,\dots, m_n$ we define $\textbf{Encode}(m)=\textbf{Int}(\mu(m_1)\parallel \dots \parallel \mu(m_n))$.

Finally, for an ASCII message $m$ we can set $$\textbf{Sign}_{sk}(m)=\textbf{Encode}(m)^d \mod N$$ $\textbf{Verify}_{pk}(m,\sigma)$ returns $1$ if and only if $\sigma^e=\textbf{Encode}(m)$.

Suppose Alice signs the message $m=$ Please pay Bob the following amount from my bank account (USD): 50. Suppose that Bob obtains $\sigma=\textbf{Sign}_{sk}(m)$. Explain how Bob can obtain a signature $\sigma'$ authorizing the bank to transfer more than $\$ 50$. How much money can Bob make? Assume that the Bank denies transfers above$750$million (USD) without in person authorization. You may assume that$\textbf{Encode}(m)<N/2^{64}$. So I am not familiar with ASCII characters. But overall, I am not sure where to begin, nor which topic I should be referring to. Can I get some help started with this question? • I think what both current answers are missing is that the mapping μ is from ASCII characters, not character codes, to bytes. So μ(0) = 00000000 implies the digit zero ("0") maps to the binary for zero. If this is the case, it does seem confusing for the question to mention ASCII at all not just say character. – jousle Jan 30 '18 at 17:16 ## 2 Answers If I read it correctly , just use the ASCII table, e.g. as given here. So "Please" is just the sequence of bytes (hexadecimal) 0x50 0x6c 0x65 0x61 0x73 0x65. Concatenation of those values gives a word (still hexadecimal, but we could have used bits as well, it's just more typing) 506c65617365 which is the decimal number$88426487575397$(using a hex to decimal conversion tool, or bc in my case). This is the number which is raised to the power$d$to create the signature of "Please". As an idea to use$(xy)^k \bmod{N} =x^k y^k \bmod{N}$for all$x,y,k$, and of course$(x^d)^e = (x^e)^d = x \bmod{N}$for all$x$. This allows for manipulation in a multiplicative way for given signatures (or encrypted values). • So I should encode the sentence using the table you provided and then raise it to a power$d$to create the signature? Then for Bob to get the bank to authorize more than$\$50$ I can append more 0's at the end of the sentence? – Username Unknown Nov 30 '17 at 0:10
• You have to modify the signature for the original (which you cannot compute) to make it into a signature for another sentence. Adding an ASCII 0 is not the same as appending a 0 in the decimal representation.@UsernameUnknown – Henno Brandsma Nov 30 '17 at 5:25

The problem can't be solved as stated. The author slipped seriously, probably confusing the digit zero (coded 30h in ASCII) and the ASCII NUL character (coded 00h). Other tweaks are required to make sense out of the problem.

$\textbf{Encode}(m)$ practically means considering the octets forming $m$ in ASCII as digits in base 256 for the result; or equivalently considering the two hexadecimal digits of each octets of $m$ in ASCII as hexadecimal digits for that result (all with usual reading order / big-endian convention). Thus if $m$ is Please pay Bob the following amount from my bank account (USD): 50. as stated, then $\textbf{Encode}(m)$ is the integer
506C656173652070617920426F622074686520666F6C6C6F77696E6720616D6F756E742066726F6D206D792062616E6B206163636F756E742028555344293A2035302Eh in hexadecimal, that is
70667586405895956254275062883015260921217928067793815399001377719049044804718166786497801733597306289791760507685871062652375121201134271473216932285286970634286 in decimal.

To make any progress, we'll need to hypothesize that:

1. the banker's software will accept the ASCII NUL character (value 00h) as the character 0 (value 30h per ASCII), for no other good reason than making sense of the problem;
2. the final dot of the message given is an artifact, or will be interpreted as a separator rather than as a decimal point by the banker (I'll assume the former, and that the message $m$ actually ends in (USD): 50 );
3. and the public exponent $e$ of the RSA public key is $3$, $5$, or $7$.

Now Bob can mount a multiplicative forgery. The general idea is that if Bob finds a positive integer $u$ such that $u^e\,\textbf{Encode}(m)=\textbf{Encode}(m')$ with $m'$ acceptable by the banker (including $\textbf{Encode}(m')<N$ necessary to pass verification anyway), then Bob can compute the signature $\sigma'$ for $m'$ as $\sigma'=u\,\sigma\bmod N$.

That signature will pass the banker's $\textbf{Verify}_{pk}(m',\sigma')$ test, because ${\sigma'}^{\,e}\bmod N$ is $(u\,\sigma)^e\bmod N$ , that is $u^e\,\sigma^e\bmod N$ , that is $u^e\,\textbf{Encode}(m)\bmod N$ , that is $u^e\,\textbf{Encode}(m)$, that is $\textbf{Encode}(m')$.

The high level of redundancy in the message practically makes it necessary that $u^e=2^{8k}$ for some integer $k$. $e$ is odd thus coprime with 8, and it follows $u$ must be of the form $2^{8l}$ with $k=el$ ($u=1$ works but is worthless as it yields $m'=m$ ).

For $e=3$, Bob can use $u=2^8$ or $u=2^{16}$ and $\textbf{Encode}(m')$ will end in ..293A203530000000h or ..293A203530000000000000h and (with the help of hypothesis 1) this may pass as Please pay Bob the following amount from my bank account (USD): 50000 or (USD): 50000000. For $e=5$ (resp. $e=7$), only $u=2^8$ will do and the attacker can get along with (USD): 5000000 (resp. (USD): 500000000).

For these $u$ and $e$, given that $\textbf{Encode}(m)<N/2^{64}$, the condition $\textbf{Encode}(m')<N$ is met. Larger $u$ or $e$ would all exceed the \$750000000 limit of the bank. How much money can Bob make? There are two reasonable possibilities: • The bank accepts a single order; Bob achieves a gain of \$49999950 for $e=3$, \$4999950 for$e=5$, \$499999950 for $e=7$ (by submitting the single message with the highest value he manages to get, instead of the original).
• The bank accepts multiple distinct orders; Bob achieves a gain of \$50050000 for$e=3$, \$5000000 for $e=5$, \$500000000 for$e=7$(by submitting several distinct acceptable messages, including the original). In the following I reject the rather artificial hypothesis 1. Now, it would be a huge surprise if Bob could make the bank accept forgeries with an amount larger than \$50 (as explicitly asked) without factoring the public modulus $N$ (or being able to do so). But that does not mean this textbook-RSA-signing scheme gets secure, even assuming a single genuine signature $\sigma$ as considered!

If the bank accepts multiple distinct orders for some definition of distinct that considers orders with different length or signatures to be distinct even if they read the same including amount, then Bob may be able to use the above technique to produce distinct messages all claiming \$50, assuming NUL is invisible on the banker's display or printout (that is likely). Bob can use$u=2^{8l}$for any positive$l$such that$2^{8el}\textbf{Encode}(m)<N$is met; no longer needs hypothesis 2; and can cope with sizably larger$e$. For example, with$N$of 2048-bit,$e=17$, Bob can use$1\le l\le11$, submit 11 messages in addition to the original, and gain \$550.

Morality is that textbook RSA signature is not a safe signature scheme, devil lies in the details, and exercises occasionally are flawed.