PrimeFactorizationRSA

Suppose you intercept the message 1027795314451781443748475386257882516 and you sus-
pect it was encrypted using RSA with n = 1029059010426758802790503300595323911 and
e = 2287529 Break the encryption and determine the original message.
You might find some of the code in the Code/RSA folder helpful for this. You might also
find that you need to use wolfram alpha to factor n (on my machine this works in a
reasonable time). Note that I have used the scheme shown in Encode/Decode to switch
between integers and strings.


a [ciphertext] = 1027795314451781443748475386257882516

n = 1029059010426758802790503300595323911

Mathematica Cryptography function; FactorInteger()
FactorInteger[1029059010426758802790503300595323911, 2]

{{216273774599027, 1}, {4758131272895389067293, 1}}
P Q

val e = 2287529
val p = 216273774599027
val q = 4758131272895389067293

( p - 1) = 216273774599026
( q - 1) = 4 758131272895389067292

φ = ( p -1 )( q-1 )
φ = 1029059010426754044659014131431657592

GCD( φ , e )
        φ                                                                                e                                                                     N                           S                                     D[private key]
1029059010426754044659014131431657592 2287529 1029059010426758802790503300595323911 -2093674                         941852144648755861760623254442258121



ModExp(a[ciphertext],D,N)
a[ciphertext] D[private key] N
1027795314451781443748475386257882516                         941852144648755861760623254442258121                 1029059010426758802790503300595323911


results in 52807870857374797201687770877083


java Decode 52807870857374797201687770877083 is...... 'Something clever' !