If you are new to Python, then here's some steps you could follow to get started with setting it up on your PC.
Short path to get Python on your PC is to download < a href="https://thonny.org/">Thonny. This is really a beginner friendly IDE. Python is attached with Thonny, so once you have Thonny on your PC, you can run any .py program on it.
To my Linux friends, the following commands can install Thonny/Python on your device:
- Raspbian
-
sudo apt install thonny - Debian
-
sudo apt install python3-tk thonny - Ubuntu
-
sudo apt install python3-tk thonny - Fedora
-
sudo dnf install python3-tkinter thonny
Bob sometimes tells Alice little secretes, and he obviously doesn't want anyone else to know what those secrets are. Therefore, Bob invented an encoding method. He would first encrypted the secret, which is in English and may contain some puncutation marks, into a list of inegers and send it and some private and public keys to Alice. The keys are going to help Alice to decrypt that integer list back to human readable languages. (Notice, even if other people know what the public key is, he/she won't be able to decrypt the message. If that person has all the keys, the decryption still cannot be done without the knowledge of RSA.)
As "Bob", you would need to decide what k and m are.
- k:
- A public key, needs to be a prime number! Usually, the bigger the k is , the safer your encryption would be.
- m:
- A product of two prime number. Again, the bigger, the better
Then, just enter the message you wish to be encrypted, and the program will output it for you:).
As "Bob", you would use the keys that Bob 👦sent to you to decrypt the integer message.
The keys are:
- k:
- A public key. It needs to be a Prime
- p:
- m is a product of two prime numbers, and p is one of the prime.
- q:
- p*q = m.
- integer message:
- This is the decrypted message that Bob 👦 sent to you. It has type string, but separated by a blank space. Therefore, we can treat it as a list.
Then, after giving the prorgam all of these, you can just wait for the program to output you the decrypted message!
If you are not familiar with how RSA works. Continuing reading is not recommanded!!! The following chunks are the implementations of those methematical theorems and algorithms in the modern computer programming languages, not for a teaching purpose.
If you survive from the warning above,let's list some of the handy maths strategies we used in this program:D
To encrypt the English message to integers, we have an ASCCI Table which has the 26 alphet Capital letters and punctuation marks with their corresponding numbers.
| A | B | C | D | E | F | G | H | I | J | K | L | M | N | O | P | Q | R | S | T | U | V | W | X | Y | Z | ! | , | . | : | ; | ' | " | ? | |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 | 22 | 23 | 24 | 25 | 26 | 27 | 28 | 29 | 30 | 31 | 32 | 33 | 34 | 35 | 36 | 37 | 38 | 39 | 40 | 41 | 42 | 43 | 44 | 45 | 46 |
The function would be straight forward once you understand the math behind it. Basically, the naive way to determine whether an integer is prime or not is to loop through all numbers between 1 and n-1 to see whether the division between it and n gives you a 0 reminder. Though we can do mod pretty fast in a modern programming language, this is still pretty slow since the time complexity is O(n) as we have n-2 numbers to check.
A quick improvement to this algorithm is to check numbers from 2 to sqrt(n). Now, to understand the reason behind this, think of the largest possible divisor of an integer, say 16. The greatest divisor of it should be 8, but this would be notified when we check if 2 is a divsor of 16, so there is no need to go all the way to 8 after we have checked 2. For number that does not have a small divisor, say 77, the largest divisor is only +4 then its smallest divisor. Therefore we conclude that, if there exist a large first divisor, then the bigger it gets, the closer it gets to the last divisor. Eventually, the first and the last would equal, and since the product of them has to be the number we are looking at, such divisor would be the square root of it.
From this, we get a time complexity worst case O(√n). This is kinda rare in computer science, and also slower than O(logn). For sure we can do other tests. for example, using Fermat's Little Theorem and that would be super fast, O(1) on average. However, the downside of it is that it never guarantees that the number is truly a prime, even you do the tests several times with different numbers. It can only tell you that the number is more likely to be a prime, yet, we never know unless we do soemthing else to verify it. But do notice when Fermat's little Theorem tells you a number isn't a prime, that is guaranteed! Good to prevent the user from entering a composite maybe, keke.
def ifprime(n):
'''
ifprime(n) takes an positive integer and returns
ture if it is a prime and false if it is not
'''
result = True
for x in range(2,int(n**(1/2))+1):
if not n%x:
result = False
break
return result
The Euclidean algorithm is a way to find the greatest common divisor of two positive integers, a and b.
I am not going to spend too much time in explaining the details of how and why this works. This algorithm is pretty elementry for anyone who took discrete mathematics or basic computer science, and yet, somewhat hard for me,a beginner too, to expain it. What I am going to do is to walk you through an example, and show you the code and the magic;)
a <- 1701 b <- 3768 do: 1701 = 0(3768) + 1701 3768 = 2(1701) + 366 1701 = 4(366) + 237 366 = 1(237) + 129 237 = 1(129) + 108 129 = 1(108) + 21 108 = 5(21) + 3 21 = 7(3) + 0 Back Track 3 = 1(108) + -5(21) 3 = 1(108) + -5(129-1(108)) =-5(129) + 6(108) 3 = -5(129) + 6(237-1(129)) =6(237) + -11(129) 3 = 6(237) + -11(366-1(237)) =-11(366) + 17(237) 3 = -11(366) + 17(1701-4(366)) =17(1701) + -79(366) 3 = 17(1701) + -79(3768-2(1701)) =-79(3768) + 175(1701) 3 = -79(3768) + 175(17010(3768)) =175(1701) + -79(3768) result <- "3=175(1701) + -79(3768)" print(result) DONE
I hope you get a good sense of how this algorithm works. Again, if you are not familiar with this, you shouldn't try to understand what RSA is and why we are using this algorithm. If you just got stuck on how this can be implemented in a modern computer language, I got you this prorgam in Python and hopefully this can help you out!.