Deciphering cypher text after breaking the RSA system

Question

I already broke the RSA system and now have the following parameters:

$m = 536813567 = 8191 \cdot 65537,$

$e = 3602561, $

$\phi(m) = 8190 \cdot 65536$

$d = 201934721$

I now want to decipher

$$\text{ARHILFKAODSTOSBSTWFQL}$$

Hint: The cypher text is given in blocks of length $7$, and every block represents a number in the "$26$-system" with $\text{A}$ representing $0$, $B$ representing $1$ and so on. The clear message does have blocks of length $6$ then.

In class, we started out with

$$c_1 = 0 \cdot 26^6 + 17 \cdot 26^5 + 7 \cdot 26^4 + 8 \cdot 26^3 + 11 \cdot 26^2 + 5 \cdot 26 + 10.$$

Then, we tried to determine

$$c_1^d \equiv 20002966 \mod m,$$

but I don't know why and how it happened.

The clear message is supposed to be "BRUCEWAYNEISBATMAN".

Answer 1

You should break it up in blocks of $7$, only you should check that the result of decoding the string to a number is $<m$.

In this case it does hold, decoding ARHILFK gives $c_1=205330408$, AODSTOS gives $c_2 = 168039786$ and finally BSTWFQL decodes as $c_3 = 531853567$ all of which are $<m$ indeed. (decoding done in Python, not very hard).

Now raising these to power $d$ modulo $m$ gives $p_1 = 20002966$, $p_2 = 11198842$ and $p_3 = 12223445$. Now encode these numbers as strings again: for $p_1$ we find the largest multiple (by a number $\le 25$) power of $26$ that is smaller or equal than $p_1$ and this is $1\cdot 26^5$, so the leftmost letter becomes $B$ (which corresponds to $1$). Substract that from $p_1$ and we are left with $8121590$. We can divide thus by $26^4$ $17$ times, with remainder $352998$. So the next letter is R (from $17$) and we go to $26^3$: $352998 =20\cdot 26^3 + 1478$ so we write down U (for $20$) and then $1478 = 2\cdot 26^2 + 126$ so we get C and finally $126 = 4 \cdot 26^1 + 22$ so the last two letters are E and W. So indeed BRUCEW is the plaintext. Note that this is 6 letters, instead of 7, but we could have used BRUCEWA which becomes the number $520077116 < m$, it's just on the limit. Stricly speaking we would have to decode as ABRUCEW and $p_2$ becomes AAYNEIS and $p_3$ becomes ABATMAN.

The initial A must then be discarded, seemingly. So maybe the plaintext should be divided up into groups of $6$ and for the output we need $6$ or $7$.

Answer 2

There are (at least) two errors. First: Your decoding of ARHILFK should be $\;\dots 5\cdot 26 + 10,$ but this is minor. Second and severe: You cannot use blocks of length 7 because $$26^7-1 = 8031810175 > m,$$ and therefore you cannot recover a valid plain text. I guess your ciphertext is computed with this invalid block length.

Using block length 6, the plaintext would be encoded as

p = "BRUCEW" = 1*26^5 + 17*26^4 + 20*26^3 + 2*26^2 + 4*26^1 + 22 = 20002966

and then $c=p^e \bmod m = 205330408.$ This would be encoded as RHILFK (looks familiar, only the leading A is dropped from your text) and then $c^d \bmod m = 20002966$, and the starting plaintext is recovered.