Exploring Public-Key Cryptography and Ancient Mathematical Techniques

Delve into the fascinating world of public-key cryptography, where the convergence of prime numbers and inverse functions plays a pivotal role in ensuring secure communication. From the history of math to contemporary applications, discover how encryption and decryption transform messages to keep them hidden from unauthorized eyes. Uncover the secrets of Egyptian multiplication and exponentiation as innovative methods in cryptography.

• Cryptography
• Public-Key
• Mathematics
• Encryption
• Ancient Techniques

kbre Follow

Uploaded on Sep 15, 2024 | 0 Views

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.

Presentation Transcript

1. Public-Key Cryptography The convergence of prime numbers, the history of math, inverse functions, and a contemporary application

2. Introduction to Cryptography Cryptography is the study of ways of writing a message that hides its meaning from everyone except the intended recipient. Encryption is a method of changing plaintext, the message to be hidden, to ciphertext, the message in its hidden form. Decryption is the procedure that changes ciphertext back to plaintext.

3. Basic Example Plaintext - MATH RULES Encryption rule - Write the plaintext backwards Ciphertext - SELUR HTAM

4. Function Example - Encrypt Choose a function that has an inverse. Rewrite the message as blocks of numbers. 2210 2917 3627 3021 1428 M A T H R U L E S Evaluate the function at each block. This becomes the encrypted message. (2210) 2(2210) 1 f = + = 4421

5. Function Example -Decrypt Find the inverse of the encryption function. This is the decryption function. 1 1 ( ) 2 2 1 = f x x Evaluate the decryption function at each received block.

6. Path to a Public Function Create a function whose inverse is extremely difficult to determine without precise details of how the function was created. Publish this function in a data base of public functions. Use the inverse function only you can determine to decrypt messages intended for you.

7. Egyptian Multiplication Find 23 26 1 26 2 52 4 104 8 208 16 416 32 > 23

8. Egyptian Multiplication 1 26 2 52 4 104 8 208 16 416

9. New Egyptian Multiplication 23 26 = 23 10111 10 2 = = L {1,1,1,0,1} L {26,52,104,208,416} 1 2 = L L Sum L L {26,52,104,0,416} 598 = 1 2 ( ) 1 2

10. Egyptian Exponentiation 23 26

11. Modular Arithmetic ( ( ) ( + ) ( ) ( = ) ( = ) a b + mod mod mod a n b n n ) a b mod mod mod a n b n n p p ( ) = mod mod a n a n

12. Modular Exponentiation 23325 mod 537 1 233 mod 537 2 2332 mod 537 = 52 mod 537 4 233 8 2338 mod 537 = 192 mod 537 = 361 mod 537 16 23316 mod 537 = 3612 mod 537 = 367 mod 537 4 mod 537 = 52 2 mod 537 = 19 mod 537

13. Modular Exponentiation 23325 mod 537 1 233 mod 537 2 2332 mod 537 = 52 mod 537 4 233 8 2338 mod 537 = 192 mod 537 = 361 mod 537 16 23316 mod 537 = 3612 mod 537 = 367 mod 537 4 mod 537 = 52 2 mod 537 = 19 mod 537

14. Modular Exponentiation Because the exponent 25 = 1 + 8 + 16, the product of the nonzero elements is

15. Public-Key Cryptography Choose two large prime numbers, p and q, and form their product n = pq. Calculate Randomly choose e such that and The values of e and n are the public key. The ciphertext, c, is c = me mod n, where m is the message being encrypted.

16. An Encryption Example Let p = 83 and q = 89. Then n = 7387. = (83 1)(89 1) = 7216 Randomly choose e = 23. Verify The encryption function is c = m23 mod 7387, where m is a plaintext message block and c is a cipher block.

17. An Encryption Example Encrypt M A T H R U L E S 2210 2917 3627 3021 1428 23 2210 mod7387 = 6117 23 = 2917 mod7387 1088 23 = 3627 mod7387 6030 23 = 3021 mod7387 1874 23 = 1428 mod7387 5878

18. Decryption Function The decryption function is m = c1255 mod 7387. 1255 6117 mod7387 = 2210 1255 = 1088 mod7387 2917 1255 = 6030 mod7387 3627 1255 = 1874 mod7387 3021 1255 = 5878 mod7387 1428

19. Public-Key Cryptography Theorem: The decryption function is given by m = cdmod n, where d is the solution of Basically, we have to prove that cd = (me mod n)d = med mod n = m.

20. Other Applications Digital signatures Olivia encrypts a message using her private key. Henry decrypts the message using her public key. Better: Olivia first encrypts her message using Henry s public key. Then uses her private key to encrypt that message. HTTPS

21. Contact Information galoisgroup@mac.com http://public.me.com/galoisgroup