The message below was encrypted using the RSA method with a modulus of n = 889 1
ID: 3184740 • Letter: T
Question
The message below was encrypted using the RSA method with a modulus of n = 889 121 and an encryption exponent of e = 5, The modulus n is a product of two primes, and your first task in decrypting the message is to find those two primes. Then, find the decryption exponent d and decipher the message: 8649615397414535842634112866461809994859412 I used a block size of 6. For ease of reading, here is the same message broken into blocks of size 6: 864961 539741 453584 263411 286646 180999 485942 Letters were converted into strings of digits by converting A to 01, B to 02, etc. Spaces were converted to 00. Each block w was encrypted, using w-we (mod n), with modulus n 889121 and encryption exponent e = 5. Your mission is to recover the original message.Explanation / Answer
%% finding p and q
n = 889121;
N_prime = primes(n^.5); %finding all the primes upto square root of n
%diving the n by each prime upto square root of n
for i = 1:length(N_prime)
if (mod(n,N_prime(i)) == 0)
j = i;
break %break the loop if we find a prime factor
end
end
p = N_prime(j);
q = n/p;
phi = (p-1)*(q-1);
%% finding decryption exponent d
x = 1;
i = 0;
while (x ==1 )
i = i+1;
if (mod((phi*i) + 1, 5) == 0)
d = (phi*i +1) /5;
break
end
end
%% decryption
block_message = [864961 539741 453584 263411 286646 180999 485942];
re = mod(block_message,n); %first remainder re
for i = 1:d-1
re = mod(re.*block_message ,n); %calculating successive remaninders because it is possible to first
%raise the numbers to the power of d then find the remainder
end
re %this is our decrypted original message
--------------------x--------------------------
output of the code;
230801 200009 190020 231500 131504 2023 150000
which can be written as 2308012000091900202315001315042023150000
if we apply the above scheme A = 01, B = 02 and so on....
then we find the following message: "What is two mod two "
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.