If you find this page and try to learn it from scratch PLEASE note that this page is just notes for myself, please watch the sources and then you can look at this page as a short summary from those videos and articles. The main sources are Eddie Woo's The RSA Encryption Algorithm, (german) task media's RSA Verschlüsselung mit Schlüsselgenerierung und Modelldurchlauf.
TLDR
- cipher = text^e % n
- text = cipher^d % n
How to generate one?
p // two prime numbers q // ^
n = p*q // yes that n
m = (p-1)*(q-1)
e // needs to be between 1 and m; needs to be a coprime with n and m
d // non-parter to m; get from d*e%m=1
little example (broken)
p=7
q=11
n=7*11=77
m=6*10=60
e=13 => 60=6*10=2*3*2*5 (cant be 2,3,5)
d*13%60=1 => d=13.923076921
from text to cipher: 2^13%77=2048%77=46
from cipher to text: 46^13.92307692%77=
little example from Eddie Woo
1. Step
p=2
q=7
2. Step
n=2*7=14
3. Step
m=(2-1)*(7-1)=6 //coprimes
4. Step
e=5 // 2,3,4,5; not 2 and 4 because no even, not 3 because 2*3=6, so it has to be 5
=> Encryption numbers: 5 and 14
5. Step
d: d*e(modm)=1
d*5(mod6)=1
25(mod6)=1
=>d=5;11 // you can choose either 5,11,17,23,...
d=11
=> Decryption numbers: 11 and 14