Changes for page Programming knowledge

Summary

• Page properties (1 modified, 0 added, 0 removed)

Details

Page properties

Content

...	...	@@ -68,59 +68,5 @@
68	68	The sequence needs to end in 1. If it does not, N is composite.
69	69	Any number in the sequence before 1 has to be another 1 or N-1. If it is, N is likely prime (although there are false positives!).
70	70
71		-= Diffie Hellman key exchange =
72		-Diffie Hellman key exchange is a key exchange algorithm that relies on both parties sharing information with each other, in such a way that they end up calculating the exact same number, without said number becoming publicly available, even if the connection is being eavesdropped on the entire time.
73	73
74		-The algorithm relies on mathematical principles that boil down to number theory. Let Alice and Bob be two parties that wish to negociate a secret key with each other over an insecure channel and Eve, an eavesdropper on said channel, is recording all of their communications with each other.
75		-
76		-To use Diffie Hellman, Alice and Bob must first agree on two public numbers: a prime number P and a generator number G which is a primitive root of P (P being prime and G being a primitive root of P are very important properties).
77		-
78		-A number g is a primitive root of N if, for every number a coprime number to N (i.e. any number that doesn't share a common divisor with N) is congruent to a power of g modulo N. That is, g is a primitive root modulo N if for every integer a coprime to N, there is some integer k for which g^^k^^ ≡ a (mod N)
79		-
80		-== Examples of primitive roots modulo N ==
81		-1. For N=2 we have generator 1.
82		-1. N=3 we have 2.
83		-1. N=5 we have 2, 3
84		-1. N=7 we have 3, 5
85		-1. N=11 we have 2, 6, 7, 8
86		-1. N=13 we have 2, 6, 7, 11
87		-1. N=17 we have 3, 5, 6, 7, 10, 11, 12, 14
88		-1. N=19 we have 2, 3, 10, 13, 14, 15
89		-1. N=23 we have 5, 7, 10, 11, 14, 15, 17, 19, 20, 21
90		-1. N=29 we have 2, 3, 8, 10, 11, 14, 15, 18, 19, 21, 26, 27
91		-1. N=31 we have 3, 11, 12, 13, 17, 21, 22, 24
92		-
93		-== Actual algorithm ==
94		-After picking a prime P and a number G primitive root modulo P (from the table above), Alice picks a random starting number that she keeps private to herself named secret,,Alice,, . Let's assume she picks 23. Bob will do the same and pick a secret number secret,,Bob,, which will be 14. Neither Bob nor Alice will share their secret numbers with each other.
95		-
96		-For the sake of this example, we shall assume that Alice and Bob chose to use N=17 and G=6 (both N and G are public at all times).
97		-Alice will calculate 6^^23^^ modulo 17=789730223053602816 modulo 17=14
98		-Alice will send this number 14 to Bob (public information).
99		-
100		-Bob will do the same and calculate 6^^14^^ modulo 17=78364164096 modulo 17=9.
101		-Bob will send Alice the number 9.
102		-
103		-Alice will then calculate 9^^23^^ modulo 17=8862938119652501095929 modulo 17 = 2
104		-
105		-Bob will then calculate 14(public information)^^14 (Bob's secret number)^^ modulo 17=11112006825558016 modulo 17=2
106		-2 is the secret that both Bob and Alice will end up calculating. Eve has no way, just by knowing the N=17, G=6 and the 14 and 9 numbers sent over the insecure channel, how to calculate this number.
107		-
108		-Since the number 2 was never sent over the encrypted channel directly, Eve will not know it.
109		-
110		-For security's sake, it is recommended that N be at least 2048 bits long.
111		-
112		-= RSA Algorithm =
113		-RSA is a public key algorithm that relies on using the principles of number theory to encrypt messages in such a way that only a specific person, owning a specific private key, can decrypt said message.
114		-
115		-Let's assume Alice wishes to send Bob a message that only Bob knows how to decrypt. In order to do so, Bob must have previously made public his personal public RSA key, which consists of two numbers: a large modulus N and another number e such that
116		-
117		-(m^^e^^)^^d^^≡ m (mod N) where m is the message.
118		-
119		-N and e must be public and not replaced or changed by malicious actors.
120		-
121		-Assuming that Alice has Bob's correct e and N public numbers, she can then send her own message m which is a number lesser than N by doing:
122		-
123		-m^^e^^ mod N = ciphertext
124		-
125		-Bob, on his side, will have precalculated N as the product of two very large primes p and q that he keeps secret. By using Carmichael's totient function on those numbers, he will calculate the missing d number that will allow him to transform the sent ciphertext back into its original m form using modular arithmetic.
126	126	)))