Decrypting RSA when given N and E but not d

Question

The cipher text is O1v3nFbVCbuZLUeJDZO9L9 using the base-64 alphabet N=15241604814814604814814604814814609737853 e=47 I know to work out d you factorize n which equals p and q then you get (p-1)(q-1) and finally e^-1 mod (p-1)(q-1) and then c^d mod N gives you the plaintext. Struggling with the base-64 side of the Question!

It seems to me you're also struggling with the finding $d$ part of the question... — Henno Brandsma, Apr 14 '18 at 22:05
If it's multiple choice (your previous question was, I gather): encrypt all the possible answers and see which one matches the observed cipher text. That way you don't need $d$. — Henno Brandsma, Apr 14 '18 at 22:11
So you could have encrypted all the possible answers, as an easier way to solve the problem. — Henno Brandsma, Apr 16 '18 at 17:20
I think the latter way was the intended way of solving the question, BTW. No $d$ or factorisation needed. — Henno Brandsma, Apr 16 '18 at 22:12

Henno Brandsma · Accepted Answer · 2018-04-14T22:10:15.747

1

Using the code in my previous answer I get as the decimal number equivalent of the ciphertext: $3473726822818613085692498216956767492477$

Wolfram alpha factorises your $N$ as

$$123457 \times 123456789123456789123456789123456829$$

This gives $$d=1297147349619189902810679264512807332559$$

and thus $$m= 42856312891220705415$$

which becomes Llanymynech (Welsh course?)

Remark:

If you know the answer is (again) a Welsh place name, take a list of them and encrypt each of them till you find a match for your ciphertext. There only a few 100 places to try at most, peanuts for computers nowadays. This already shows that the scheme is quite flawed in this form, even with larger $N$ (this one is tiny by realistic scenarios), as with such public key schemes random padding is added to elimate such attack scenarios.

edited Apr 14 '18 at 22:10

answered Apr 14 '18 at 14:58

Henno Brandsma

242,131

How do i convert to Base 64 then? – Pkr96 Apr 14 '18 at 16:03
@Pkr96 post the number, I'll convert it back – Henno Brandsma Apr 14 '18 at 16:09
So the number is 3473726822818613085692498216956767492477^648573674809593865210809024512 mod 15241604814814604814814604814814609737853 – Pkr96 Apr 14 '18 at 16:17
@Pkr96 your numbers are wrong, see my answer – Henno Brandsma Apr 14 '18 at 16:25
Thanks a lot..What am i doing wrong in the calculation? – Pkr96 Apr 14 '18 at 17:35
@Pkr96 post your calculations. What tools do you have to work with large numbers? – Henno Brandsma Apr 14 '18 at 17:59

Decrypting RSA when given N and E but not d

1 Answers1