Understanding RSA Encryption for Secure Communication
Encryption plays a vital role in securing information, and RSA encryption, developed by Rivest, Shamir, and Adleman in 1977, uses public and private keys to safeguard data. Learn about the process, challenges with other encryption methods, prime numbers, and how RSA encryption works step by step.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
E N D
Presentation Transcript
Public Key Cryptography Nathan Gingrich and Joanie Davis
What is Encryption? Encryption is the process of converting information or data into code, especially to prevent unauthorized access
Problems With Other Encryption Systems Caesar Cipher Shift the alphabet down a certain number Data Encryption Standard Exchange keys privately to encode messages All other methods of Encryption required a private exchange of data to establish the encryption methods
Math Review Prime Numbers A Number that only has two factors (1 and itself) Mod Operator A Mod (B) is the remainder of the division A / B Relatively Prime Two numbers that only have 1 as a common factor
More Math Euler s Totient: The number of relatively prime numbers there are to n that are less than n. Denoted phi(n) If N = Q * P, where P and Q are prime, then phi(N) = (P -1) * (Q -1) If a and n are relatively prime, then aphi(n)= 1 mod(n)
RSA Published in 1977 Ron Rivest, Adi Shamir, Leonard Adleman Uses publically shared keys to encrypt a message Uses privately held keys to decrypt a message Security lies in the difficulty of factoring very large numbers
How It Works 1.Generate the Clock 2.Choose E and D 3.Share Public Key 4.Encode message and send 5.Receive message and decode
Generate the Clock The Clock is the value you will plug into the modulus function Select two large prime numbers P and Q Multiply P and Q together to determine clock size N = P * Q
Choose E and D E -Public Encryption Key D -Private Decryption Key Start by calculating Z Z = (P -1) * (Q -1) Determine E and D such that E * D mod ( Z ) = 1
Find K to Determine E and D Generate a list of potential K values such that K mod ( Z ) = 1 Factor potential K values until one is not prime and has a pair of factors that are relatively prime E and D are those relatively prime factors Share your public encryption key E Keep decryption key D private
Sending a Message Obtain the receiver s public encryption key E1 Divide the message into blocks of size less than N Encode each block M into encoded block C C = ME1mod (N) Send the encoded messages
Decoding A Message For each encoded message segment C Decrypt C to decoded message string M using your own private decryption key D M = CD mod (N)
Why It Works M = CD (By definition of Decryption) = MED (By Definition of Encryption) = MK * (Q -1) * (P -1) + 1 (Since ED = K * (Q -1) * (P -1) + 1) = MK phi(N) + 1 (Fact of Euler s Totient) = ( MK phi(N) )k* M (Equivalency) = M (Another fact of Euler s Totient)
Send/Receive Example Goal: Encrypt and send the message Hello Generate the Clock P = 1123 Q = 1913 Determine N and Z N = P * Q = 1123 * 1913 = 2148299
Send/Receive Example Cont. Find candidates for K such that K mod (Z) = 1 Sample of generated examples: 2145265, 4290529, 6435793, 8581057, 10726321 K = 2145265 Use factors of K to determine E and D Factors of K = 5, 71, 355, 6043, 30215, 429053 E = 355
Send/Receive Example Cont. Message to send: Hello Message converted to ASCII encoding: 072 101 108 108 111 072101355mod (2148299) = 257217 108108355mod (2148299) = 1705479 111355mod (2148299) = 1580437 Encrypted message String: 025721717054791580437 Decrypted message String: 072101108108111
Intercept Example You intercept the encrypted message: 172899202185711270741 The N and E values used to encrypt are publically known N: 1887839 E: 773 Goal: determine the D value to decrypt the message
Intercept Example Cont. Factor N to determine P and Q N = 1887839 = 1009 * 1871 Use P and Q to determine Z Z = 1008 * 1870 = 1884960
Intercept Example Cont. Knowing Z, guess values of K (potential values of K mod (Z) = 1) 1884961, 3769921, 5654881, 7539841, 9424801, 11309761, 13194721, 15079681 For each potential K, divide by E to get a potential D 1884961 / 773 = 2438.5006468 3769921 / 773 = 4877 5654881 / 773 = 7315.499
Intercept Example Cont. For potential D = 4877, attempt decoding Result String: 072 101 108 108 111 ASCII Conversion: Hello For incorrect D = 2438 Result String = |
Activities Go to RSA Sandbox (link on class website) Follow the steps and generate your own N, E, and D Practice encrypting some messages
Group Activity Cont. Get into groups of 3 or 4 Have everyone in the group exchange public keys and clock size Select two group members to communicate with encrypted messages. Publically share the encrypted strings Other group members should attempt to determine the receiver s decryption key to read the messages
Real World Example n = 119294134840169509055527211331255649644606569661527638012067481954943056851150333806315957037 715620297305000118628770846689969112892212245457118060574995989517080042105263427376322274266 393116193517839570773505632231596681121927337473973220312512599061231322250945506260066557538 238517575390621262940383913963 (309 digits) p = 109337661836325758176115170347306682871557999846322234541387456711212734562876700082908433028 75521274970245314593222946129064538358581018615539828479146469 q = 109106169673491102317237340786149226453370608821417489682098342251389760111799933942998101597 36904468554021708289824396553412180514827996444845438176099727 This is a good way to send a private key for a symmetrical algorithm like DES or AES, which are faster.
