GSR Journal Georgetown Scientific Research Journal Volume 1 | Edition 2 July 31, 2021 Danya Adams ISSN 2767-6420 5 Danya Adams � An Investigation Into the Mathematics of Decryption Techniques in RSA Encryption, With an Implementation in Python Sofia Flynn Volume One Edition Two Spring 2021 GEORGETOWN SCIENTIFIC RESEARCH JOURNAL 6 Georgetown Scientific Research Journal An Investigation Into the Mathematics of Decryption Techniques in RSA Encryption, With an Implementation in Python Sofia Flynn Department of Mathematics, Georgetown University, Washington D.C. E-mail: smf133@georgetown.edu https://doi.org/10.48091/gsr.v1i2.18 Abstract This study explores the mathematics of two different techniques that can be used to access the decryption key in RSA encryption including semi-prime factorization and a logarithmic method. The study then presents a Python program, written by the author, that automates the calculations for either of the decryption techniques and also calculates the number of iterations required to determine the decryption key in either circumstance. Most importantly, the program utilizes only values of the RSA encryption algorithm that would be made publicly available in actual circumstances to calculate the decryption key so as to mimic real-life occurrences with as much integrity and accuracy as possible. Keywords: RSA encryption, semi-prime factorization, decryption, Python 1. Introduction RSA encryption was created in the 1970s as an asymmetric (public-key) form of cryptography that would replace the then-commonly utilized and weakening symmetric cryptography.1 In symmetric cryptography, in order to exchange secret messages, two individuals would either have to meet beforehand to exchange identical keys or run the risk of their keys being intercepted.2 In a simplified example of symmetric cryptography, suppose “Bob” wanted to send a secret message to “Alice.” Alice and Bob would first have to meet each other to share identical keys that would be used for encryption and decryption, ensuring that each person ultimately possesses the same key. Using one of the identical keys, Bob could then encrypt his secret message and send it to Alice, who would then decrypt the message using the other identical key that she and Bob had exchanged beforehand. If Bob and Alice cannot meet to share keys, then Bob would have to send the key that decrypts his encrypted message along with his encrypted message to Alice, running the risk that a third party could easily intercept both the encrypted message and key before it comes into Alice’s possession. In 1970, James Ellis proposed a hypothetical idea in which secret messages could be exchanged between individuals without them having to meet beforehand to share identical keys, thereby eliminating dependence on the ever-weakening symmetric cryptography.3 The premise was simple: if Bob wished to send a secret message to Alice, Alice could create a lock and a key that decrypted, or “unlocked’, that lock. Alice could then send the open lock to Bob, who would proceed to encrypt, or “lock”, his secret message using the open lock. Alice would retain possession of the key that decrypted the lock. Bob would then send his encrypted message to Alice, who would decrypt it using the key that remained in her possession throughout the entire process. Such is the conceptual idea behind asymmetric 7 Georgetown Scientific Research Journal cryptography; by preventing an initial exchange of keys, one avoids the risk of a third party intercepting the key used to decrypt the encrypted message. In 1973, Clifford Cocks invented a mathematical implementation of Ellis’ idea, which had remained classified for twenty-four years.4 Later on in 1977, Ron Rivest, Adi Shamir, and Leonard Adleman created the equivalent of Cocks’ implementation of Ellis’ idea completely independently.5 The algorithm they created based on Ellis’ conceptual idea about asymmetric cryptography was henceforth known as RSA (each of the founders’ initials) encryption and is widely used today. RSA has formidable strength; as of yet, the only device that is considered to be capable of breaking RSA is a quantum computer.6 Rivest, Shamir, and Adleman’s algorithm consists of six values that correspond to either a public or private key. The public key is released publicly and can be used by anyone to encrypt a message; the private key, on the other hand, is kept hidden by the “key generator” (the person who creates the public and private key values; the equivalent of “Alice” in the latter example above) and is used by the key generator to decrypt any encrypted message sent to him or her. The six values generated by the key generator are denoted: P, Q, N, 𝜑𝜑N, E, and D. P, Q, 𝜑𝜑N, and D belong to the private key and are kept secret by the key generator. N and E belong to the public key and are released publicly. The key generator must generate values for P, Q, N, 𝜑𝜑N, E, and D. The key generator must first choose two large prime numbers P and Q. In real world utilizations of RSA encryption, these prime numbers are typically large, usually hundreds of digits long. The key generator must then multiply these two prime numbers together to attain the value of N, that is, P x Q = N. N is a semi-prime number, or the product of two prime numbers. Next, the key generator calculates the 𝜑𝜑 or “phi” of N. The phi of a number outputs how many positive integers are less than that number that do not share any common factors greater than one with the number. For example, to find the phi of nine, a key generator would list all of the integers less than nine but greater than or equal to one (eight, seven, six, five, four, three, two, one). From this list, they would then evaluate which integers share common factors with nine that are greater than one. Six and three both share common factors greater than one with nine while eight, seven, five, four, two, and one do not share any common factors greater than one with nine. The phi of nine is six because there are six integers less than nine that do not share any common factors greater than one with nine. Calculating the phi of N is straightforward for the key generator due to the fact that the phi function is multiplicative, meaning that: 𝜑𝜑N = 𝜑𝜑P x 𝜑𝜑Q (equation 1) or the phi of N is equivalent to the phi of each of N’s factors multiplied together. This property can be proved using the Chinese Remainder Theorem but such a proof is omitted in this paper.7 Thus, the key generator can calculate the phi of P and the phi of Q and multiply these two values together to attain the phi of N. The phi of any prime number is simply one less than the original prime number because the only factors that prime numbers have are one and itself.8 For example, the phi of five (a prime number) is four because there are four positive integers less than five that do not share any common factors greater than one with five. Thus, the phi of the prime number P is (P – 1) and the phi of the prime number Q is (Q – 1). Thus, the phi of the semi-prime N is (P – 1)*(Q – 1). To generate E, the key generator must pick an integer that satisfies the requirement: 1 < E < 𝜑𝜑N; E shares no common factors with 𝜑𝜑N. Finally, to generate D, the key generator must pick an integer that satisfies the requirement: (E*D) mod 𝜑𝜑N = 1 (equation 2) The operation “mod” outputs the remainder of a division. For example, 8 mod 6 = 2 because the remainder of the division eight divided by six is two. Once the key generator has generated values for P, Q, N, 𝜑𝜑N, E, and D, they must release the values of N and E (the public key values) to the 8 Georgetown Scientific Research Journal public but retain the values of P, Q, 𝜑𝜑N, and D (the private key values). If a person (the “sender”; the equivalent of “Bob” in the latter example above) wishes to send a secret message to the key generator, they can use the values of N and E to encrypt their message using the expression: !mod N, where M is the secret message to be encrypted. The sender would then send this encrypted message !mod N (the result of which is known as “C”, for ciphertext message) to the key generator. The key generator can then decrypt the encrypted message C by using the private key value of D through the expression: "mod N. The result of "mod N yields the original message M. Thus, in summary: !mod N = C (equation 3) and "mod N = M (equation 4) with proof of correctness derived by Rivest, Shamir, and Adleman using Fermat’s Little Theorem in their publication. As can be seen, RSA encryption functions similarly to the simplified example of asymmetric encryption given earlier (Introduction, paragraph two). Alice, the key generator, creates a public and private key containing the values of P, Q, N, 𝜑𝜑N, E, and D. N and E function as the values that Bob uses to lock the open lock that Alice created and sent to him, while the values of P, Q, 𝜑𝜑N, and D function as the key that opens the lock once Bob locks it with his message and sends it to Alice. Although publicly releasing the values of N and E does not detract from the strength of asymmetric RSA encryption, it is integral that the values of P, Q, 𝜑𝜑N, and D remain hidden and can only be accessed by the key generator: this is because RSA encryption was built around two main assumptions that make it safe and acceptable to release the values of N and E publicly. First, it is exceedingly time-consuming to calculate the decryption key (D) by factoring large semi-prime numbers. Second, it is exceedingly time- consuming to calculate the decryption key (D) using properties of logarithms because of the discrete logarithm problem. If the decryption key D was accessed by a person other than the key generator, then this person would be able to intercept secret encrypted messages meant for the key generator and decrypt them using the intercepted value of D. In short, RSA is a secure cryptosystem because accessing the decryption key by semi-prime factorization or logarithmic properties both prove to be too time-consuming to be pursued realistically, at least until the advent of quantum computing. If a “message-interceptor” (the equivalent of a “hacker”) wants to calculate the value of the decryption key using only the publicly-available values of N and E, they have two options, with the first being semi-prime factorization.9 When semi- prime factorization is used by a message- interceptor in an attempt to gain access to the decryption key, the magnitude of the semi-prime number proves to be of paramount importance in preventing the message-interceptor from calculating the decryption key. In the case of RSA encryption, the semi-prime number is N (the product of the two prime numbers P and Q), whose value is publicly available to the message- interceptor. The message-interceptor must factor the semi-prime number N into its constituent factors P and Q. From there, the message- interceptor can plug in the values of P and Q into the expression (P – 1)*(Q – 1) to find 𝜑𝜑N. After having attained the value of 𝜑𝜑N, the message- interceptor, knowing that (E*D) must equal 1 more than 𝜑𝜑N in order to achieve a modular relationship with 1 as a remainder, can plug this value along with the public key value of E into equation 2 and solve for D. For example, if E is 7 and 𝜑𝜑N is 3120, then the formula would be: 7D mod 3120 = 1, and thus, 7D must equal 3121 for the relationship to work. With this in mind, the message-interceptor can easily solve for D: 7D = 3121 D = 445.857143 . . . D, however, must be an integer value. In order to satisfy this rule, the message-interceptor can look for other modular relationships that yield a remainder of 1. For example, 6241 mod 6240 =1. 9 Georgetown Scientific Research Journal Similarly, 9361 mod 9360 = 1. The message- interceptor can keep on multiplying the value of 3120 by increasing integers to achieve different modular relationships that will still yield 1 as a remainder until D is an integer value. Example: 7D mod (3120*1) = 1; 7D = 3120*1 + 1; D = (3120*1 + 1)/7; D = decimal 7D mod (3120*2) = 1; 7D = 3120*2 + 1; D = (3120*2 + 1)/7; D = decimal 7D mod (3120*3) = 1; 7D = 3120*3 + 1; D = (3120*3 + 1)/7; D = decimal 7D mod (3120*4) = 1; 7D = 3120*4 + 1; D = (3120*4 + 1)/7; D = integer Here, solving for D only requires 4 iterations. The formula for solving for D simplifies to: D = 𝜑𝜑N* 𝜑𝜑NMultiplier + 1)/E (equation 5) where 𝜑𝜑NMultiplier” is a specific integer value that the message-interceptor multiplies 𝜑𝜑N by to achieve different modular relationships that yield 1. With knowledge of the publicly-available value of E as well as the value of 𝜑𝜑N, the message- interceptor can easily calculate the value of the decryption key, D, having created one equation with only one unknown value. However, one problem exists: factoring N into its constituent factors P and Q becomes increasingly time- consuming as N grows. This is why large prime numbers had to be chosen by the key generator as values for P and Q. The larger N is (the product of the already large values of P and Q), the more time it will take to factor it. In RSA, the types of semi-prime numbers utilized are typically around 600 digits long. Semi-prime numbers of such magnitudes take a huge amount of time to factor using current technologies. In fact, in 1978, Rivest, Shamir, and Adleman predicted that factoring a 500-digit semi-prime number would take approximately 4.2 x years to factor using the Schroeppel factoring algorithm.10 Therefore, due to the immense amount of time needed to factor N into its constituent factors P and Q, it is impractical for a message-interceptor to use semi- prime factorization to calculate the decryption key, D.11 The second option that the message- interceptor has if he wishes to calculate the value of the decryption key using only the publicly available values of N and E is to use the properties of logarithms. Recall that encrypting a message requires plugging a secret message M into the expression !mod N, and thus decrypting that message requires plugging in the result of !mod N (which is C) into the expression "mod N to attain the original message M. The message- interceptor, like all others, has access to the public key values of N and E. He can generate a secret integer message M and plug it into the expression !mod N to attain the ciphertext/encrypted message C. Then, they can plug the value of C along with the public key value of N into the expression "mod N. The message-interceptor knows that the result of "mod N must equal his original message M (see equation 4). The message-interceptor has knowledge of the value of N (a public value) as well as C and M, because he generated these values. Therefore, the message- interceptor has created an equation in which only one unknown, D, the decryption key, exists. For example, if N is 143 and E is 7, and the message- interceptor picks his secret message M to be 24, then the enciphered message would be mod 143, or 106. The message-interceptor can plug in the values of 143 (N), 24 (M) and 106 (C) into equation 4, yielding "mod 143 = 24, and subsequently solve for D. Knowing that " must equal to 143 + 24, or 167, for the above equation to work due to modular arithmetic (167 mod 143 = 24), the message-interceptor can set " to 167. Knowing that " = 167, the message-interceptor can easily solve for D using the properties of logarithms: " = 167 log " = log 167 D (log 106) = log 167 D = log 167/log 106 D = 1.09747 . . . 10 I I I I I I I I Georgetown Scientific Research Journal However, D has the restriction that it must be an integer value, which the above value is not. Thus, the message-interceptor needs to come up with another way to calculate D using this method. The message-interceptor knows that 167 mod 143 = 24, but there are other values that, when divided by each other, will yield a remainder of 24. 143 multiplied by 2 is 286. 286 plus 24 is 310. Thus, 310 mod 286 = 24. Similarly, 143 multiplied by 3 is 429. 429 plus 24 is 453. Thus, 453 mod 429 = 24. The message-interceptor can keep on multiplying the value of 143 by increasing integers to achieve different modular relationships that will still yield 24 as a remainder until D is an integer value. Example: " mod (143*1) = 24; " = (143*1) + 24; log( " = log(143*1 +24); D = log(143*1 + 24)/log(106); D = decimal " mod (143*2) = 24; " = (143*2) + 24; log( " = log(143*2 +24); D = log(143*2 + 24)/log(106); D = decimal " mod (143*3) = 24; " = (143*3) + 24; log( " = log(143*3 +24); D = log(143*3 + 24)/log(106); D = decimal The formula for solving for D in this way can be simplified to: D = log(N*NMultiplier + M)/log(C) (equation 6) where “NMultiplier” is the increasing integer by which the message-interceptor multiplies N to achieve different modular relationships that will still yield the secret message, M. Even though the message-interceptor can keep on running this type of sequence to achieve an integer value for D, the amount of iterations it would take to finally attain an integer value for D is astronomical, making the logarithmic decryption key calculations just as impractical and time-consuming as semi-prime factorization. The difficulty of calculating the exponent D in this way is known as the discrete logarithm problem, or the “RSA problem.” Decryption through semi-prime factorization and decryption through logarithmic properties are both processes that are referred to as “trapdoor one-way functions”.12 Trapdoor one-way functions are easy to compute in one direction but difficult to compute in the other direction unless special “trapdoor” information is known. In the case of decryption through semi-prime factorization, Rivest, Shamir, and Aldeman realized that it was trivially easy to multiply two large prime numbers P and Q together yet infinitely more difficult and time-consuming to factor the resulting semi-prime number, N. Similarly, they realized that it was easy to calculate M in equation 4 given the values of C, N, and most importantly, D, but far more arduous to calculate the value of D in equation 4 given the values of C, N, and M. These two utilizations of trapdoor one- way functions in RSA encryption are what make it so formidably strong and currently unbreakable without a quantum computer.13 In the case of decryption through either semi- prime factorization or logarithmic properties, an immense number of iterations are required to finally attain the decryption key, D. In the case of semi-prime factorization, if every integer less than the semi-prime number, N, and greater than or equal to two was tested to see if it divided evenly into N, the number of iterations required would be N – 2. If N is a huge semi-prime number that is hundreds of digits long, the number of iterations required to factor N would be two subtracted from the huge semi-prime number. While it is true that not all the numbers less than N would have to be assessed if it was certain that N was semi-prime (because this would narrow the numbers that needed to be tested down to only prime numbers), if access to a large bank of prime numbers is not unattainable (as in this project), all integers greater than or equal to two and less than N would still have to be tested to see if they divide evenly into N, making the expression for the amount of iterations needed to factor N in this project N – 2. In the algorithm presented for factoring N in this manner, time complexity is O(N). In the case of decryption through logarithmic properties, ("#$%)∗( iterations are required to acquire D. Because the formula for solving for D through 11 I I I I I I I I I I I I Georgetown Scientific Research Journal logarithmic techniques can be simplified to equation 6, where “NMultiplier” is the increasing integers the message-interceptor multiplies N by to achieve different modular relationships that will still yield the secret message, M, “NMultiplier” can be isolated and solved for to attain the number of iterations it would take to solve for D. The following demonstrates the process of isolating “NMultiplier” from the equation D = log(N*NMultiplier + M)/log(C): D = log(N*NMultiplier + M)/log(C) D*[log(C)] = log(N*NMultiplier + M) = N*NMultiplier + M – M = N*NMultiplier NMultiplier = ∗ ( ) (equation 7) By solving for “NMultiplier”, the number of iterations needed to calculate D through logarithmic techniques has been calculated to be ∗ ( ) . Because this program allows a maximum of one million iterations to compute D in this manner, the associated time complexity is less than O(1000000). The purpose of this research study is to discuss the function of a program built using Python that calculates the decryption key using semi-prime factorization as well as the logarithmic method. Further, the program calculates the number of iterations required to calculate D using either of these methods, indicating the efficacy and advantageousness of using one method over the other in different circumstances. This research study will delve into explaining the code written in the program and how it contributes to achieving the end result of decryption as well as the number of iterations derived necessary to calculate D using either of the aforementioned methods, being that of semi-prime factorization or logarithms. 2. Materials 2.1 Required Materials: Python programming system installed on MacBook laptop or other personal computer, complete with IDLE and running module. Access to Python’s “math” module located in Python’s standard library. The module includes mathematical functions necessary to the operation of the program. 2.1 Recommended Materials: Access to a computational knowledge/answer engine like Wolfram Alpha used to initially verify the accuracy of the results obtained from the program.14 12 Georgetown Scientific Research Journal 2. Methods/Procedures Figure 1. Code script 3.1 The Code Behind Semi-Prime Factorization to Calculate D (Lines 1-47) 3.1.1 Factoring N In lines 3 – 9, the program asks for a semi- prime input which it then sets to the variable N. The program is designed to test all integers less than N but greater than or equal to two to determine whether they divide evenly into N. An integer is a factor of N if the remainder of N divided by said integer equals zero. The integers that do divide evenly into N are deemed to be factors of N and are appended to a list called “NFactorsList”. In lines 10 – 20, the program forces another input to be given for N if the first input is not a semi-prime number. If the length of NFactorsList is only four, this indicates that N is a semi-prime number because semi-prime numbers only have four factors: one, the semi-prime itself, and the two prime numbers multiplied together to attain the semi-prime number. In lines 21 – 25, after ensuring a semi-prime input for N, the program sets the variables P and Q to the two prime numbers that N is divisible by. 3.1.2 Factoring 𝜑𝜑N In lines 26 – 27, the program sets the variable PhiN to (P – 1)*(Q – 1) based on the mathematics described in the introduction for the calculation of 𝜑𝜑N. 3.1.3 Generating a public key value for E In lines 34 – 40, the program initializes a list called “PhiNFactorsList” that lists the factors of the value of 𝜑𝜑N by testing which integers are greater than two but less than 𝜑𝜑N and yield a remainder of zero when divided into 𝜑𝜑N. In lines 41 – 42, the program initializes a list called “PrimesLessThan100List” which lists all of the prime numbers less than 100 and also initializes that variable E by setting it to a placeholder value of 1. 13 11"°"'1m""" 2 l'nnl "IJIUtYl'l1O, lllllOUUJI Sl'.MJ-l'IU.\IE fAt:l'ORJZA'llO~ l lnltl21l2tVl!Uble, •ul. •-Li>t• 1, N 5Slartlooo 6 7 8 forllll-,1m111UtC{2.Nl lfNm>di•O AddllO :F>aonl.J""' in"!l"I' &,pa Dclc,c NFa:unLi,i u 15 Addl,NioNFaamList Sbnloop 16 17 18 19 20Endloop 21 Siar, b-c, ?2 23 24 2.1 Endloop For inlq,cn i in n1f1P.C (2. N) If modi 0 For lm'll'ff I In 111¥tC (2, N) If ""'1i-O lnitiolize\'•riollleQ i fni1lltlin: ,.uiatE P • NK) Add i IO NFanli>t 26 lrumlrze ,onollle l'hlN (P 1)'(0 I) 27 End loop 28 lcitimr "'W1H Pt-quals • "P •" 291citimr"'"'M~-"Q-" JO lru1labz£ Sl!102 I,_,~. -,'In N •• JI 1'nn1 l'lxilals followed by I' 32PrimQ,quakfol1-dbyQ Jl Prim Plu,~ual, fol.._.. by Pili: 34 lnitializc li,t l'lliNFIICIOnli,t - I. l'bil 351Jcktc clanall, 0-2 m l'lnNfllda'SLl5t .16Sun loop 17 38 Forim'!P'lln~(2,l'l!IN) lfl'h,,"lmodi•O 39 40Endloop AddilOl'bil IC10rW5I 41 lnitlallzc (jg Pr!mesLestlb:lnlootJg • 2, 3, 5, 7, II, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 71, 73, 79, 83, 89, 97 42 lnitialw:m.tblc E-1 -OSian loco 44 4.~ 46 ,fl 48 49Fm•up ll'bileE•I lfflN dcmcnof'Prina.f ~,Thant(k)(jsi is nn1 in Phi1'"Factordi~ E- firq clara11 rlPrimcd °''ThlnlOOl j~ Else Delele lir.;t elemOlll of PrimosLesslbonlOOList !:4) lnitiali1e 51:~ r-.a,nk -~-,. 51 l'nnl !:,cpols followed by E 52 lnitializc ,'Driable P!u,~1u!tipller Sls..t~ ~ 5S 561:ndloop 111,ilc: (((l'h;s:',lull~ia'PhN) + l)IF.) m-.1 1 dur,; rwl apnl 0 P!u,'c\tllll>her Plu.~Mulbpbor+ I ~ lcitimr ma1bk D • ((P!,L"Mdtiplicr'Pbi),,i + I )'1! 58 lcitimr "'W1H ~--o-" '!D l'nnl UoQuab fol1-d by u 60 l'nnl "OOUlYl'llO:S 'lllR()IJ(j]I LUGARIUL\l!>~ 61 lnitlallzcwrublc M=U!ff-¢,ffllm-lnpn 61 lmtiilli:« v&blt- C • M r.mt'd tu I.Ir E pw,a- all au! N 6l lnitializc lllrinR Moctuab • "Scatt mcssa,;c • • 641Mlabz£ Sl!102CcciuAl,•"l:nc:mllodlllWllllC •• 65 Prim~ fblmod by M <,6 Prim Caiwl, folk>wod by C 67 lnitializc wt Noo!ntc,.aDLi31 • I, 2 68 Delde all elemom or Nonlnlqpl)Li 73 lf((loj(N•, .!ultiplier+M))'!IOR()JC))mod I doesDOIOQualO 74 AM((icftN' .fultiplia+M)~)10 l.._nl.is1 'IS iltiplia-1,'\luhiplia + 1 71> Else D2 ((iot(N'NMultiplier•M)}~) 77 711Fmh~ 791f02-1 IIO Pnnl ·u More thoo • rmllm 11er.111mS io col......_. 81 Else 82 PrintD2 Ill Pri,. ,IOW MA rmRA11C1'."l"" 84 lrutlall2o stnn2 lbrouobSan1l'runol'IICt"'120b0n "lleraoons uswt sam oruno fac1onzlwon • as l!!ltl2ll2r RriDJ! ~ = ·,- U!fflll lotlarithms = • 86 lcitimr .-.-ia,blc l1er,6tnM•Sc:uiPrim:Faruriatiw • N -2 117 l'nnl 11rcqd,SamJ'nm:l'ICIOnlll!JOO follov,,:d by l1a11KmVIIScmJ'nm:l'aclaUllllOll 8111Mlabz£V1Nblcl1a0110mVi&Lol>•{(I0IOUx:(ioltOll,~un-Ml'N 89 Prim lll'OUJ!hu,pllhm fblm'ed by ltmdoosViJLoll' Georgetown Scientific Research Journal In lines 43 – 49, the program generates a value for E, which must be greater than 1, less than 𝜑𝜑N, and share no common factors with 𝜑𝜑N. The program cross-checks values in the PrimesLessThan100List against values in the PhiNFactorsList until it finds a value in the PrimesLessThan100List that is not in the PhiNFactorsList, which it then sets it to the variable E. By checking primes as possible values for E against the factors of 𝜑𝜑N, the program ensures that whatever value it picks for E shares no common factors with 𝜑𝜑N. 3.1.4 Generating D In lines 52 – 56, the program sets a variable called “PhiNMultiplier” to 1, which will act as 𝜑𝜑NMultiplier in equation 5. While D does not equal an integer solution, the program continuously adds 1 to the value of PhiNMultiplier. When PhiNMultiplier iterates enough that it yields an integer value for D, the program sets D to 𝜑𝜑N* 𝜑𝜑NMultiplier + 1)/E, where 𝜑𝜑NMultiplier represents the number of iterations it took to yield an integer solution for D. 3.2 The Code Behind Logarithmic Techniques to Calculate D (Lines 48 – 71) In lines 61 – 62, the program asks for an integer input and sets it to the variable M. It then encrypts M by raising it to the value of E, dividing the entire expression by N, and taking the modulus of the division, which is C, the ciphertext message. In lines 67 – 82, the program initializes a variable called “NMultiplier” to 1 which acts as NMultiplier in equation 6. Because Python has a limited capacity for running large numbers of iterations, the program continuously adds 1 to NMultiplier until NMultiplier = 1000000 (the first million iterations) instead of until D is an integer. When NMultiplier = 1000000, although D might not be an integer, the program still cuts off at this point and prints that D takes more than one million iterations to calculate. All non-integer numbers resulting from log(N*NMultiplier + M)/log(C) are appended to the list “NonIntegerDList” and stored. 3.3 The Code Behind Iterations for Semi-Prime Factorization to Calculate D and Logarithmic Techniques to Calculate D (Lines 72 – 80) In lines 86 – 89, the iterations for decryption using semi-prime factorization and for decryption using logarithmic techniques are both calculated using the expressions N – 2 and ("#$%)∗( , respectively (see introduction of derivation of iterations). The program then prints the number of iterations needed in either case, allowing for quick comparison of either method’s effectiveness in different circumstances. 4. Results Figure 2. Program yield The creation of the Python code described on the previous pages (Figure 1) resulted in a program that, when run, yielded the above result (Figure 2). Lines 1 – 9 print each of the values necessary to calculate the decryption key, D, through semi- prime factorization. In line 2, the program asks for a semi-prime number input. If a number that is not semi-prime is inputted, as in Figure 2 when 1500 was inputted, the program asks for another semi-prime value instead, displaying the message “Your prior input was not a semi-prime number. 14 0 DECRYPTION THROUGH SEMI-PRIME FACTORIZATION 0 Enter a semi-prime number: 1500 0 Your prior input was not a semi-prime number. Enter a semi-prime number: 1820 G Your prior input was not a semi-prime number. Enter a semi-prime number: 143 • p ■ 11 • Q. 13 Q Phi N • 120 0 E • 7 0 D • 103 G) DECRYPTION THROUGH LOGARITHMS 4D Enter a secret message to encrypt: 24 G Secret message • 24 0 Encrypted message • 106 G, D • More than o million iterations to calculate fD HOW MANY ITERATIONS? G Iterations using semi-prime factorization ■ 141 4D Iterations using logarithms • 2.8Z597349859519e+Z06 Georgetown Scientific Research Journal Enter a semi-prime number:” until a semi-prime value has been given. When a semi-prime value is given, this number is factored into its constituent factors, P and Q, which are then printed. 𝜑𝜑N is then calculated by plugging P and Q into the expression (P – 1)*(Q – 1) and subsequently printed. Once a public key value E is generated and printed, D is solved for in equation 2 and printed. Lines 10 – 14 print the necessary information to calculate D through logarithms. In line 11, the program asks for an integer message M, prints M in line 12, prints C (the value of M, encrypted) in line 13, and prints D in line 14 by solving for it in equation 4. However, in all the times that the program has been run, it has never been able to calculate D through logarithms due to the fact that it would take an incredible amount of iterations to do this. Instead, the program prints, “D = more than a million iterations to calculate” if it cannot calculate D through logarithms in under a million iterations. Finally, in lines 15 – 17, the program prints the number of iterations that the program needs to calculate D in either instance. On occasion, the program will experience an overflow error when it tries to calculate the iterations for decryption through logarithms because Python does not have the capacity for such huge calculations. This project would be economically feasible to implement as it would not cost anything to download an app version of this program onto a mobile device once a graphical user interface has been created for all of the code that has been written. 5. Discussion and Conclusions The research study undertaken was largely successful because it met all of the objectives defined in the introduction: to describe the mathematics of decryption techniques, to create a program capable of calculating the decryption key in RSA using two different methods and calculating the number of iterations required to accomplish this in either instance, and to explain the code written in the program and its roles in ultimately achieving the end result of decryption. The program has the capacity to calculate the decryption key through both semi-prime factorization and through the logarithmic method. That being said, the logarithmic method almost always takes too many iterations to feasibly calculate the decryption key because of the exponentiation operations involved. However, the program is still theoretically capable of calculating the decryption key through the logarithmic method. The program is also capable of calculating the number of iterations needed to calculate D through either method but will at times experience an overflow error if the number of iterations needed to calculate D through logarithmic techniques exceeds Python’s programming capacity. If the code in this study can be replicated using more powerful and faster programs, it would be surmised that D would be calculated with more rapidity through the logarithmic technique and the program would not experience overflow errors. When such errors occur, exception handling can be used to catch the errors using Python’s OverflowError. Such an implementation is provided in the appendix. Additionally, there are many other techniques in existence to factor large semi-prime numbers, though this program only makes use of one of the most rudimentary such techniques. The quadratic sieve and the general number field sieve are two such integer factorization algorithms that far outstrip the technique presented in this research.15 Further, this program could have possible implementations in the future. Because it is capable of calculating the number of iterations needed to obtain the decryption key through either semi-prime factorization or logarithms, the program could potentially be used as a starting point to create an entirely new study in which the efficacy of either decryption method is compared when certain variables like the length of the semi- prime number N or the public exponent E are varied. 15 Georgetown Scientific Research Journal Acknowledgements I would like to offer my thanks to Dr. Michal Kolpak and Mr. Quillian Haralson for inspiring this project, as well as to the myriad other friends, educators, and family who have given their encouragement and support in the creation of this and many other projects. References 1. Luciano, D., Prichett, G. (1987). Cryptology: from Caesar ciphers to public-key cryptosystems. The College Mathematics Journal, 18(1), 2-17. https://doi.org/10.2307/2686311. 2. Deffs, H., Helmut, K. Introduction to Cryptography, Principles and Applications 2nd ed. (2007). Springer. 11-31. 3. Ellis, J. H. (1970). The possibility of secure non- secret digital encryption. UK Communications Electronics Security Group. www.cesg.gov.uk/site/publications/media/possnse. pdf. _________. (1999). The history of non-secret encryption. Cryptologia 23(3) 267–73. http:// www.informaworld.com/10.1080/0161- 119991887919. 4. Cocks, C. C. (1973). A Note on non-secret encryption. UK Communications Electronics Security Group. http://www.cesg.gov.uk/publications/media /notense.pdf. 5. Rivest, R. L., Shamir, A., Adleman, L. (1977). A method for obtaining digital signatures and public- key cryptosystems. Technical Memo Number MIT-LCS-TM-082. MIT. http://publications .csail.mit.edu/lcs/specpub.php?id=81. 6. Holden, J. (2017). The Mathematics of Secrets: Cryptography from Caesar Ciphers to Digital Encryption. Princeton University Press. 216. 7. Dence, J. B., Dence, T. P. (1999). Elements of the Theory of Numbers. Harcourt Academic Press. 156. 8. https://mathworld.wolfram.com/PrimeNumber.ht ml. Retrieved March 1, 2021. 9. Wagstaff, S. (2013). The Joy of Factoring. American Mathematical Society. 195–202. 10. Rivest, R. L., Shamir, A., Adleman, L. (1978). A method for obtaining digital signatures and public- key cryptosystems. Communications of the Association for Computing Machinery, 21(2). 11. Gardner, Martin. (1977). Mathematical games: A new kind of cipher that would take millions of years to break. Scientific American 237(2) 120–24. https://simson.net/ref/1977/Gardner_RSA.pdf. 12. Diffie, W., Hellman, M. (1976). New directions in cryptography. IEEE Transactions on Information Theory, 22 (6): 644–654. https://doi.org/10.1109/TIT.1976.1055638 13. Gidney, C., Ekerå, M. (2021). How to factor 2048 bit RSA integers in 8 hours using 20 million noisy qubits. Quantum 5. (433). arXvix: 1905.09749v3. https://doi.org/10.22331/q-2021- 04-15-433. 14. https://www.wolframalpha.com/ 15. Pomerance, C. (1996). A tale of two sieves. Notices of the American Mathematical Society. 43 (12). 1473–1485. 16 Georgetown Scientific Research Journal 17 Appendix An implementation of the program in pseudocode is provided below in which exception handling is used to handle overflow errors. Georgetown Scientific Research Journal 18 73 Danya Adams Danya Adams � GSR Journal Georgetown Scientific Research Journal Table of Contents Letter From the Editors An Investigation Into theMathematics of DecryptionTechniques in RSA Encryption,With an Implementation in Python GPR40 and Postsynaptic NMDAReceptors: A Pair AgainstEpilepsy The Burn Behind the Bullet:Understanding Black Mothers’Experiences After Losing a Childto Gun Violence in Washington,DC-Baltimore City MetropolitanRegion Cancer Models to Defeat TherapyResistance in Pancreatic DuctalAdenocarcinoma Meet the Authors Meet the Staff Acknowledgments