Changes for page Programming knowledge

Summary

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

Details

Page properties

Content

...	...	@@ -68,5 +68,59 @@
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.
71	71
	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.
72	72	)))