Good Day,
I am attempting to curate ciphertext using RSA encryption given values for the message to encrypt using the encryption algorithm:
$c = m^e Mod N$
I understand the elements that go into performing the encryption/decryption of the cipher using RSA, however, my course has only taught a singular method of determining the ciphertext give the public key and $e$ which is modular exponentiation.
Modular exponentiation works fine until you deal with an $e$ of significant size.
For example convert "15" to ciphertext:
Where $N=319$ $m=15$ and $e=17$
Using successive squaring $15^1, 15^2, 15^4.. 15^{16}$ I eventually land on the cipher being 192 for the message $m=15$ after using successive squaring until the exponent is 16, stopping execution when the exponent is 16 as to not overflow past 17, then converting 17 to base 2 in order to derive the ciphertext value wherein each value of 1 in the binary expansion of 17 equates to a value from the successive squaring technique.
My question here is what are alternate methods to obtain the cipher text when dealing with large exponents?
For example using the acii table to convert values into ciphertext:
Converting "NO" into a cipher where $m=7879$ $N=373097$ and $e=459173$
effectively the algorithm then becomes: $(7879)^{459173}$ $Mod$ $373097$
It seems inconceivable to even attempt to utilize successive squaring with an exponent of 459173. My course has this as a question and I am stumped and feeling rather down..
I was feeling rather confident in dealing with Euclidean and extended Euclidean algorithm, multiplicative inverse's etc.. and modular exponentiation (successive squaring), however, I am now doubting my existence whilst dealing with this. My course seems to just expect us to be able to obtain the answer, yet I do not know of a more efficient method of determining what the ciphertext would be.
If anyone can help point me in the right direction I would be very appreciative..
Best Answer
Your answer for $\ 15^{17}\pmod{319}\ $ is incorrect. It should be $192$. Here are the steps: \begin{align} 15^2&=225\\ 15^4&\equiv225^2=50625\equiv223\pmod{319}\\ 15^8&\equiv223^2=49729\equiv284\pmod{319}\\ 15^{16}&\equiv284^2=80656\equiv268\pmod{319}\\ 15^{17}&=15\cdot15^{16}\equiv15\cdot268\\ &=4020\equiv192\pmod{319}\ . \end{align} As you can see from the above series of relations, your answer of $223$ is $\ 15^4\pmod{319}\ $, not $\ 15^{17}\pmod{319}\ $
Computing $\ 7879^{459173}\pmod{373097}\ $ by successively squaring $7879$ mod $373097$ is not all that difficult with a calculator. Doing it by hand with just a pencil and paper, however, isn't something I'd ever want to try, or something that should be expected of students in any course on the subject. While it should only require an hour or two, it would be a fairly pointless and error-prone exercise. Anything of value you might learn by doing it could be just as well picked up by doing the computations with a calculator, or by writing a computer program or script to do them.
Since $\ 459173=2^{18}+2^{17}+2^{16}+2^8+2^7+2^5+2^2+1\ $, computing the necessary squares of $\ 7879\pmod{373097}\ $ requires only $17$ multiplications mod $373097$ and multiplying them together then requires only $7$ more.