Notes - The ElGamal Public Key Cryptosystem

The following are notes from Introduction to Cyrptography with Coding Theory.

• ElGamal Public Key Cryptosystem
• Alice wants to send a message m to Bob
• Bob chooses a large prime p and a primitive root α
• Bob chooses a secret integer a and computes B ≡ α ^a (mod p)
• Make public (p, α, B) and is Bob's public key
• Alice
• downloads (p, α, B)
• Chooses a secret random integer k and computes r ≡ α ^k (mod p)
• Computes t ≡ B ^k m (mod p)
• sends the pair (r,t) to B
• Bob decrypts by computing tr ^-a ≡ m (mod p)
• Security
• depends on a being kept secret which is reliant on the idea that discrete logs are difficult to compute

Back to ToC

Notes - Discrete Logarithms

The following are notes from Introduction to Cyrptography with Coding Theory.

• RSA Algorithm relies on the difficulty of factoring, but we can also use the difficulty of discrete logs
• Fix a prime p. Let α and Β be nonzero integers mod p and suppose
• Β ≡ α^x (mod p)
• It is difficult to find x assuming we choose a large enough prime
• α is taken to be a primitive root mod p so that every Β is a power of α (mod p)
• The size of the largest primes for which discrete logs can be computed is usually about the same size as the largest integers that could be factored
• This means that discrete logs are another example of one-way functions
• where f(x) is easy to compute but given y it is computationally infeasible to find x

Back to ToC

Notes - An Application to Treaty Verification

The following are notes from Introduction to Cyrptography with Coding Theory.

• This method will essentially describe the RSA signature Scheme
• Example
• Countries A and B have signed a nuclear test ban treaty
• Country A wants to verify the treaty by placing sensors in B
• Country A wants to ensure sensors are sending correct data without tampering
• Country B wants to look at the message before its being sent to ensure that espionage data is not being transmitted
• A chooses n = pq to be the product of two large primes and chooses encryption/decryption exponents e and d
•  n and e are given to B but p q and d are kept secret
• sensor collects data x and uses d to encrypt x to y ≡ x^d (mod n)
• both x and y are sent to country B to check that y^e ≡ x (mod n) and then to Country A to ensure that the number x has not been modified. If x was modified it would be the same difficulty as decrypting the rsa message x

Back to ToC

Notes - The RSA Algorithm

The following are notes from Introduction to Cryptography with Coding Theory.

• Public Key Cryptosystem
• Presented by Diffie-Hellman
• Goal - allow Alice to send a message to Bob without previous contact and without the use of a courier to exchange a key but protect the message from Eve a potential attacker
• The RSA Algorithm
• Bob chooses secret primes p and q and computes n = pq
• Bob chooses e with gcd(e, (p-1)(q-1)) = 1
• Bob computes d with de ≡ 1 (mod(p-1)(q-1))
• Bob makes n and e public, and keeps p, q, d secret
• Alice encrypts m as c ≡ m^e (mod n) and sends c to Bob
• Bob decrypts by computing m ≡ c^d (mod n)
• Example of the RSA Algorithm
• p = 885320963, q = 238855417
• n = p * q = 211463707796206571
• Let the encryption exponent be e = 9007
• Let the sample message m be 30120
• c  ≡ m^e ≡ 30120⁹⁰⁰⁷ ≡ 113535859035722866 (mod n)
• Where c stands for the ciphertext Alice is sending to Bob
• Bob knows p and q so he knows (p-1)(q-1) then he uses the extended euclidean algorithm to compute d such that de ≡ 1  mod (p-1)(q-1)
• d = 116402471153538991
• Bob computes c^d ≡ 113535859035722866^{116402471153538991} ≡ 30120 (mod n) to obtain the original message

Back to ToC

Notes - Square Roots Mod n

The following are notes from Introduction to Cryptography with Coding Theory.

• Suppose we are told that x² ≡ 71 (mod 77) has a solution
• How do we find one solution/all solutions?
• Proposition
• if y has a square root mod p, then teh square roots of y mod p are +-x.
• If y has no square root mod p, then -y has a square root mod p, and the square roots of -y are +-x
• Example
• Lets find the square roots of 5 mod 11. Since (P+1)/4 = 3, we compute x ≡ 5³ ≡ 4 (mod 11). Since 4² ≡ 5 (mod 11), the square roots of 5 mod 11 are +-4 or 5,7 mod 11
• Let's try to find the square root of 2 mod 11. Since (p+1)/4 = 3, we compute 2³ ≡ 8 (mod 11). But 8² ≡ 9 ≡ -2 (mod 11), so we have found a square root of -2 rather than 2
• Example
• Composite Modulus square roots
• x² ≡ 71 (mod 77)
• x² ≡ 71 ≡ 1 (mod 7) and x² ≡ 71 ≡ 5 (mod 11)
• x ≡ +-1 (mod 7) and x ≡ +-4 (mod 11)
• The chinese remainder theorem tells us that a congruence mod 7 and a congruence mod 11 can be recombined into a congruence mod 77
• m₁ = 7, m₂ = 11, m = m₁m₂ = 77
• M₁ = m/m₁= 11, M₂ = m/m₂= 7
• M₁N₁ ≡ 1 (mod m₁₎ => 11 N₁ ≡ 1 (mod 7) => 4 N₁ ≡ 1 (mod 7) => N₁ ≡ 2 (mod 7)
• this will get us results of x ≡ +-15,+-29 (mod 77) 

Back to ToC

Notes - Primitive Roots

The following are notes from Introduction to Cryptography with Coding Theory.

• Consider the powers of 3 (mod 7)
• 3¹≡ 3, 3²≡ 2, 3³≡ 6, 3⁴≡ 4, 3⁵≡ 5, 3⁶≡ 1
• Note that we obtain all nonzero congruence classes mod 7 as powers of 3
• Generally when p is a prime, a primitive root mod p is a number whose powers yield every nonzero class mod p
• Primitive Roots
• Let g be a primitive root for the prime p
• Let n be an integer. Then gⁿ≡ 1 (mod p) if and only if n ≡ 0 (mod p - 1)
• If j and k are integers, then g^j ≡ g^j (mod p) if and only if j ≡ k (mod p - 1)

Back to ToC

Notes - Fermat's Little Theorem and Euler's Theorem

The following are notes from Introduction to Cryptography with Coding Theory.

• Fermat's Little Theorem
• if p is a prime and p does not divide a, then
• a ^p-1≡ (1 mod p)
• Example
• 2¹⁰ = 1024 ≡ 1 (mod 11)
• can then evaluate 2⁵³ (mod 11)
• 2⁵³ = (2¹⁰)⁵2³ ≡ 1⁵2³  ≡ 8 (mod 11)
• We now require an analog for composite modulus n
• Define φ(n) as the number of integers a between 1 and n such that gcd(a,n) = 1
• Example
• φ(10) = 4 [1,3,7,9]
• Also can be deduced from chinese remainder theorem
• φ(n) = n Π_p|n (1-1/p)
• φ(p) = p - 1 where p is a prime number
• when n = pq where p and q are primes φ(pq) = (p - 1)(q - 1)
• Euler's Theorem
• If gcd(a,n) = 1, then a^φ(n) ≡ 1 (mod n)
• Example
• What are the last 3 digits of 7⁸⁰³
• same as working mod 1000
• 1000 = 2³5³
• φ(1000) = 1000(1-1/2)(1-1/5) = 400
• Example
• Compute 2⁴³²¹⁰  (mod 101)
• Note that 101 is prime, therefore 2¹⁰⁰  ≡ 1 (mod 101)
• Therefore (2¹⁰⁰)⁴³²2¹⁰ = 1⁴³²2¹⁰ ≡ 1024 (mod 101) ≡ 14

Back to ToC

Notes - The Chinese Remainder Theorem

The following are notes from Introduction to Cryptography with Coding Theory.

• Chinese remainder theorem is used to break a congruence mod n into a system of congruences mod factors of n
• Example
• Number satisfies x≡ 25(mod 42)
• means we can write x = 25 + 42k (k is some integer)
• we can rewrite 42 as 7*6
• x = 25 + 7(6k)
• x = 25 + 6(7k)
• Chinese Remainder Theorem
• suppose gcd(m,n) = 1. If an integer c is a multiple of both m and n, then c is a multiple of mn. given integers a and b there exists exactly one solution x (mod mn)to the simultaneous congruences
• x ≡ a (mod m)
• x ≡ a (mod m)
• x ≡ b (mod n)
• Lemma
• Let m,n be integers with gcd(m,n) = 1
• if an integer c is a multiple of both m and n, then c is a multiple of mn
• Example
• Solve x ≡ 3 (mod 7), x ≡ 5 (mod 15)
• 7*15 = 105
• list congruences
• 5,20,35,50,65,80
• 3,10,17,24,31,38,45,52,59,66,73,80
• x ≡ 80 mod 105
• solve
• nk ≡ a - b (mod m)
• k ≡ (a - b)i (mod m) [i is the multiplicative inverse of n]

Back to ToC

Notes - Pseudo-random Bit Generation

The following are notes from Introduction to Cryptography with Coding Theory.

• Ways to generate random bits
• sampling thermal noise from semiconductor resistor
• flipping coins
• Sampling natural processes however is very slow and its difficult to ensure that the enemy does not view the process
• Pseudo-Random generation
• example rand()
• takes a seed as an input produces output bitstream
• based on linear congruential generators
• x_n = a x _n-1 + b (mod m)
• number x₀ is the initial seed
• this is suitable for experimental purposes but not for cryptographic purposes because it is too predictable
• one way functions
• functions f(x) that are easy to compute but is computationally infeasible to determine y = f(x)
• therefore we can define a x_j = f(s+j) for j = 1,2,3
• DES, SHA
• Blum-Blum Shub pseudo-random bit generator
• quadratic residue generator
• generate two large primes p, q that are congruent to 3 mod 4
• then set n = pq and chose random integer x that is relatively prie to n
• BBS produces a sequence by
• x_j ≡ x²_j-1 (mod n)
• b_j is the least significant bit of x_j
• However BBS is slow to calculate due to size of primes

Back to ToC

Notes - Block Cipher

The following are notes from Introduction to Cryptography with Coding Theory.

• also known as the hill cipher
• choose an integer n, the key is an n x n matrix
• M =
• (1   2 3)
• (4   5 6)
• (11 9 8)
• Message is written as a series of row vectors
• abc becomes (0 1 2) which gets 
• (012)(1   2 3)
•         (4   5 6)
•         (11 9 8)
• mod 26
• (0,23,22)
• In order to decrypt we need the determinant of matrix M to satisfy
• gcd(det(M),26)=1
• Find the inverse of matrix M
•       (-14 11 -3)
• -1/3(34 -25  6)
•       (-19 13 -3)
• Since 17 is the inverse of -3 mod 26
•      (22 5  1 )
•      (6 17 24)
•      (15 13 1)
• can return plaintext by mulitplying inverse matrix by (0,23,22) mod 26
• In order to perform the block cipher we just divide the plaintext into blocks of n characters and if the ciphertext does not divide evenly, the blanks are left as 0 but the matrix multiplication is still done
• changing one letter changes n letters of plaintext therefore frequency decryption is very difficult
• Claude Shannon
• the fundamental foundations of cryptography include
• Diffusion
• means that changing one character of the plaintext, then several characters
• Confusion
• means that key does not relate in a simple way to the ciphertext
• each ciphertext should depend on several parts of the key

Back to ToC

Notes - The Vigenere Cipher

The following are notes from Introduction to Cryptography with Coding Theory.

• A variation of the shift cipher
• key for the encryption is a vector of a chosen length
• Example
• key length 6
• (21,4,2,19,14,17)
• corresponds to word vector
• To encrypt we shift by the word vector
• A known plain text attack will succeed if enough characters are known
• Cryptanalysis uses the fact that english letter frequency is not equal
• a - 0.082
• b - 0.015
• c - 0.028
• d - 0.043
• e - 0.127
• f - 0.022
• g - 0.020
• h - 0.061
• i - 0.070
• j - 0.002
• k - 0.008
• l - 0.040
• m - 0.024
• n - 0.067
• o - 0.075
• p - 0.019
• q - 0.001
• r - 0.060
• s - 0.063
• t - 0.091
• u - 0.028
• v - 0.010
• w - 0.023
• x - 0.001
• y - 0.020
• z - 0.001
• Variations can occur but usually takes effort to produce, example the book Gadsby does not contain the letter e
• However, when using a Vigenere Cipher the frequencies are distributed so that the above is not nearly as useful in decryption
• Finding Key Length
• We find the key length by matching the number of coincidences
• write the ciphertext, then rewrite it with a displacement
• Example
•     VVHQ
• VVHQW
• Then we mark each time there is a match between the two rows, and after trying multiple displacements the largest number of coincidences will be closest to the key length
• Finding the Key: First Method
• take a look at the 1+5n letters and find the frequency of letters then repeat for 2+5n, 3+5n, 4+5n, 5+5n we then guess at the code by finding the difference between the most frequent letter and e to find the overall shift that is used as the key
• After finding the key we then test it by decrypting to confirm if the key was correct
• Soft Proof
• place the frequencies of the english letters into a vector A₀ and let A_i represent the frequencies shifted by i
• When taking the dot product of these two vectors we arrive at 0.066 with a full match but significantly less than that for any other shift
• We can also use this knowledge to approximate the number of coincidences we should find for a given match, which would be 0.066*the number of comparisons

Back to ToC

Notes - Substitution Ciphers

The following are notes from Introduction to Cryptography with Coding Theory.

• Shift and Affine ciphers are examples of substitution ciphers Vigenere and Hill Ciphers are not
• Substitution Ciphers can be broken by a frequency count but how exactly does the process go?
• Approximate Frequencies of letters in english
• e - 0.127
• t - 0.091
• a - 0.082
• o - 0.075
• i - 0.070
• n - 0.067
• s - 0.063
• h - 0.061
• r - 0.060
• With the exception of E the other letters are close enough that for a small sample we would not be able to decide which is which therefore we need to look at pairs of letters
• e often contacts many low-frequency characters
• a, i, o tend to avoid one other
• n has around 80% chase to be preceded with vowels
• h often appears before e and rarely after it
• most common digram is th
• r pairs more with vowels than s among the frequent letters
• combination rn should appear more than nr
• to is more common than ot
• Proceeding applying these rules, it is necessary to decrypt the message through recognizing partial words within the text to figure out the key for low frequency letters

Back to ToC

Notes - Affine Ciphers

The following are notes from Introduction to Cryptography with Coding Theory.

• This is a strengthened version of a shift cipher where x -> ax+B
• example a = 9, B = 2
• affine -> CVVWPM
• Decryption involves reversing the cipher
• y = 9 x + 2
• In modular arithmetic we need to find the inverse differently than we would in algebra, more clearly described in Chapter 3
• Since we are using the alphabet, we need to work with mod 26
• therefore we need to find gcd(9,26) = 1
• What we can do is use the extended euclidean algorithm to solve for a multiplier to 9 that would result 1 mod 26 aka
• 9 x ≡ 1 (mod 26)
• we can also see that multiplying 9 by 3 will also result in a remainder of 1 which satisfies this congruence
• Therefore 3 is the desired inverse
• x ≡ 3(y-2) ≡ 3y -6 ≡ 3y +20 (mod 26)
• Example
• map the letter V
• V = 21
• 3*21 +20
• 81
• 81 ≡ 5 mod(26)
• the letter f
• This decryption will allow us to return the plaintext of affine from CVVWPM
• We must be able to find the inverse in modular arithmetic in order to have a usable key so arbitrary keys may result in multiple returns for a singular input
• Possible Attacks
• Ciphertext only
• 312 keys only means its easy for a computer to break, however difficult by hand
• Known Plaintext
• knowing even some of the plaintext reduces the possibilities and can potentially result in breaking the code even without a computer
• Chosen Plaintext
•  if ab is chosen as plaintext we can immediately break the code
• Chosen Ciphertext
• again if AB is chosen as ciphertext we find the encryption key but we already have the decryption key in this case so no additional work is needed

Back to ToC

Notes - Modular Exponentiation

The following are notes from Introduction to Cryptography with Coding Theory.

• We will often be looking at numbers in the form of
•  x^a(mod n)
• suppose we want to compute 2¹²³⁴(mod 789)
• start with 2² ≡ 4(mod 789) repeatedly square the sides
• 2⁴ ≡ 4² ≡ 16
• 2⁸ ≡ 16² ≡ 256
• 2¹⁶ ≡ 256² ≡ 49
• 2³² ≡  34
• 2⁶⁴ ≡  367
• 2¹²⁸ ≡  559
• 2²⁵⁶ ≡  37
• 2⁵¹² ≡  580
• 2¹⁰²⁴ ≡  286
• since 1234 = 1024 + 128 + 64 + 16 + 2
• 2¹²³⁴ ≡ 286 * 559 * 367 * 49 * 4 ≡ 481 (mod 789)
• never had to deal with number larger than 788^2

Back to ToC

Notes - Congruences

The following are notes from Introduction to Cryptography with Coding Theory.

• Modular Arithmetic or Congruences
• Let a, b, n be integers with n ≠ 0 
• a ≡ b (mod n) 
• read as a is congruent to b mod n if a-b is a mutliple of n
• or congruent if a and b differ by a multiple of n
• can be rewritten as a = b + nk for some integer k
• Examples
• 32 ≡ 7 mod 5
• -12 ≡ 37 mod 7
• Proposition
• let a, b, c, n be integers with n ≠ 0
• a ≡ 0 mod n if and only if n|a
• a ≡ a mod n 
• a ≡ b mod n
• if a ≡ b and b ≡ c mod n, then a ≡ c mod n
• Proposition
• let a, b, c, d, n be integers with n ≠ 0 and suppose a ≡ b mod n and c ≡ d mod n
• then a + c = b + d, a - c = b - d, ac ≡ bd mod n
• Modulo operations
• addition - we add them as integers then if the product is less than n we stop, if the product is larger than n-1 then we divide by n and take the remainder. 
• subtraction - same as addition
• multiplication- same as addition
• note -  we can use negative but usually use positive integers
• division
• let a, b, c, d, n be integers with n ≠ 0 and with gcd(a,n)=1. If ab ≡ ac mod n then b ≡ c mod n. In other words, if a and n are relatively prime,we can divide both sides of the congruence by a
• Examples
• Solve 2x + 7 ≡ 3 mod 17
• 2x ≡ -4
• x ≡ -2 ≡ 15
• division allowed because gcd(2,17) = 1
• Solve 5x + 6 ≡ 13 mod 11
• 5x ≡ 7
• 7 ≡ 18 ≡ 29 ≡ 40
• 5x ≡ 7 is equivalent to 5x ≡ 40
• x ≡ 8 mod 11
• Proposition
• Suppose gcd(a,n) = 1. Let s and t be integers such that as + nt = 1. (They can be found via the extended euclidean algorithm) Then as = 1 mod n, so s is the multiplicative inverse for a mod n
• Example
• solve 11,111x ≡ 4 mod 12,345
• gcd
• 12,345 = 1 * 11,111 + 1,234
• 11,111 = 9 * 1,234 + 5
• 1234 = 246 * 5 + 4
• 5 = 1 * 4 + 1
• 4 = 4 * 1 + 0
• Extended Euclidean Method
• x₀ = 0
• x₁ = 1
• x₂ = -1 * 1 + 0 = -1
• x₃ = -9 * -1 + 1 = 10
• x₄ = -246 * 10  + -1 = -2461
• x₅ = -1 * -2461  + 10 = 2471
• Therefore
• 11111 * 2471 + 12345 * y₅ = 1
• 11111 * 2471 ≡ 1 (mod 12345)
• multiple original 11111x ≡ 4 by 2471 to get
• x ≡ 9884 (mod 12345)
• Summary
• Finding a^-1 (mod n)
• use extended euclidean algorithm to find integers s and t such that as + nt = 1
• a^-1 ≡ s (mod n)
• Solving ax ≡ c (mod n) when gcd(a,n) = 1
• use the extended euclidean algorithm to find as + nt = 1
• the solution is x ≡ cs (mod n)
• What if gcd(a,n)>1?
• If d does not divide b, there is no solution
• assume d|b consider the new congruence
• (a/d)x ≡ b/d (mod n/d)
• solve above to obtain solution x₀
• the solutions of original congruence ax ≡ b (mod n)
• x_0, x₀ + (n/d), x₀ + 2(n/d),...., x₀+(d-1)(n/d) mod n
• Example
• solve 12x ≡ 21 (mod 39)
• gcd (12,39) =3
• divide by 3
• 4x ≡ 7 (mod 13)
• we can get a x₀ of 5 through trial and error or the extended euclidean method
• we get two more solutions by adding 39/3 once then twice to obtain 18 and 31 as other answers.

Back to ToC

Notes - Solving AX+ BY = D

The following are notes from Introduction to Cryptography with Coding Theory.

• In a previous example we used the Euclidean Algorithm to find the GCD 
• We will now show how we can get the integers x,y that fulfill
• ax + by = gcd(a,b)
• Example gcd(482,1180)
• 1180 = 2 * 482 +216
• 482 = 2 * 216 + 50
• 216 = 4 * 50 + 16
• 50 = 3 * 16 + 2
• 16 = 8 * 2 + 0
• Which gave us q₁ = 2, q₂ = 2, q₃ = 4, q₄ = 3, q₅ = 8
• We will now use the following sequences
• x₀ = 0, x₁ = 1, x_j = -q_j-1 x_j-1 + x_j-2
• y₀ = 1, y₁ = 0, y_j = -q_j-1 y_j-1 + y_j-2
• In order to arrive at
• x₀ = 0
• x₁ = 1
• x₂ = -2 x₁ + x₀ = -2
• x₃ = -2 x₂ + x₁ = 5
• x₄ = -4 x₃ + x₂ = -22
• x₅ = -3 x₄ + x₃ = 71
• y₅ would be calculated similarly to arrive at -29
• We would then plug this in to ax + by = gcd(a,b)
• 482 * 71 + 1180 * (-29)
• 2
• This is often called the extended Euclidean algorithm
• used for congruences

Back to ToC

Notes - One-Time Pads

The following are notes from Introduction to Cryptography with Coding Theory.

• One-Time Pad is an unbreakable cryptosystem developed by Gilbert Vernam and Joseph Mauborgne 1918
• Key is a random sequence of 0,1 same length as the message and are added together with XOR aka exclusive or
• Example
• plaintext  00101001
• key         10101100
• ciphertext 10000101
• Decryption uses the same key, add teh key onto the ciphertext to return the plaintext
• If used on the alphabet, the key is a random sequence of shifts between 0 to 25
• unbreakable for ciphertext only attack
• if we only have a piece of plaintext, the random generation means we know nothing about the rest of the key
• Issues
• truly random generation
• trusted courier
• key is very long, dangerous to reuse
• Trivia
• hotline between washington and USSR was thought to be a one-time pad
• Variation of one time pad
• satellite produce and broadcast several random sequences of bits at a rate fast enough that no computer can store more than a very small faction of the outputs
• Alice wants to send message to bob
• use RSA to agree on a method to sample bits from the random bit streams, use these bits to generate a key for a one time pad
• Attacker Eve cannot decrypt because by the time she knows about the message the stream has disappeared

Back to ToC

Notes - Basic Notions

The following are notes from Introduction to Cryptography with Coding Theory.

• Divisibility
• let a and b be integers with a ≠ 0. a divides b if there is an integer k such that b = ak, or that b is a multiple of a. This is denoted by a|b
• 3|15, -15|60
• Proposition
• for every a ≠ 0, a|0 and a|a. Also, 1|b for every b
• if a|b and b|c, then a|c
• if a|b and a|c then a|(sb + tc) for all integers s and t
• Prime Numbers
• A number p > 1 that is divisible by only 1 and itself is a prime number, any number that is not prime is called composite
• Prime Number Theorem
• Let π(x) ~ x/(ln x) where π(x) is the number of primes less than x in the sense that π(x)/x/(ln x) ->1 as x->
• Example
• 100 digit primes
• π(10¹⁰⁰) - π(10⁹⁹) ~ 10¹⁰⁰/(ln 10¹⁰⁰) - 10⁹⁹/(ln 10⁹⁹) ~ 3.9 x 10⁹⁷
• Theorem - Every Positive Integer is a product of primes, and this factorization is unique up to a reordering of the factors
• Lemma - If p is a prime and p divides a product of integers ab, then either p|a or p|b. More generally if a prime p divides a product ab...z then p must divide one of the factors a,b,...z
• Therefore an integer can be written as the product of its prime factors to a given power
• Greatest Common Divisor
• GCD is the largest positive integer dividing both a and b
• example gcd(6,4)=2; gcd(24,60)  = 12
• Factor both numbers into primes, and take the smallest of the common divisors and multiply them together
• Euclidean algorithm
• Example gcd(482,1180)
• 1180 = 2 * 482 +216
• 482 = 2 * 216 + 50
• 216 = 4 * 50 + 16
• 50 = 3 * 16 + 2
• 16 = 8 * 2 + 0
• Since 2 was the last nonzero remainder, the gcd is 2
• divide a by b in the form
• a = q₁ b + r₁
• if r = 0 then b divides a and the greatest common divisor is b if r ≠ 0 then continue with
• b = q₂ r₁+ r₂
• r_k-2= q_k r_k-1 + r_k
• r_k-1= q_k+1 r_k 
• gcd(a,b) = r_k
• Theorem - Let a and b be two integers with at least one of a,b nonzero, and let d = gcd(a,b). Then there exist integers x, y such that ax + by = d. In particular, if a and b are relatively prime, then there exist integers x,y with ax + by = 1.
• Corollary - If p is a prime and p divides a product of integers ab,then either p|a or p|b. More generally if a prime p divides a product ab,...z then p must divide one of the factors a,b,...z

Back to ToC

Notes - Shift Ciphers

The following are notes from Introduction to Cryptography with Coding Theory.

• Shift ciphers are one of the earliest cryptosystems and is attributed to Julius Caesar
• gaul is divided into three parts
• he then shifts each letter by 3 places
• JDXOLVGLYLGHGLQWRWKUHHSDUWV
• Encryption process is then x -> x + k where k = 3
• Attackers methodology
• Ciphertext only
• If the method is known then there are only 26 possible keys. However there is most likely more than one meaningful message that can be found when using these keys.
• Frequency analysis to see the shift, e is the most common letter in the English language, find the difference between the most common letter in the message and e
• Known Plaintext
• if you know one letter of plaintext the key is broken
• Chosen Plaintext
• again inputting even just one letter will give you the key
• Chosen Ciphertext
• seeing the output of an input will give you the key

Back  to ToC

Notes - Classical Cryptosystems

The following are notes from Introduction to Cryptography with Coding Theory.

• For simple cryptosystems we can make a few conventions
• plaintext is written in lowercase
• CIPHERTEXT written in uppercase
• Letters of the alphabet are assigned numbers from 0-25 starting from a
• Spaces and punctuation are omitted

Back to ToC