Slide 1Modern CryptographyMulti-Precision CalculatorThat’s a lot of digitsModular ArithmeticExamplesAdditionSubtractionMultiplicationDivisionDivision by Multiplicative InverseUseful FunctionsGreatest Common DivisorGCD ExampleGCD ResultsExtended Euclidean AlgorithmExtended Euclid ExampleFinding the MMIModular ExponentiationExponentiation ExampleModular Exponentiation ExampleConsider MultiplicationChinese Remainder TheoremHow To CRTCRT Pre-calculationsCRT Pre-calculations tooCRT AdditionCRT MultiplicationEuler’s Totient FunctionPhi ExamplesPublic Key Cryptography - RSAHow to RSAWhy Does RSA WorkRSA and CRTRSA ExampleRSA-CRT Pre-calculationsRSA EncryptRSA-CRT DecryptHow to Share a SecretWhy It Is SecretPaillier CryptographyHow to PaillierPaillier EncryptPaillier DecryptThe Generator gDecrypt NumeratorDecrypt DenominatorThe Decrypt ResultCryptographic BlindingPaillier BlindingTallying the VoteHomomorphic PaillierReferences CitedReferences continuedThe Algebra of EncryptionCS 6910 Semester Research and ProjectUniversity of Colorado at Colorado SpringsBy Cliff McCullough18 July 2011Modern Cryptography 7/16/2011 Cliff McCullough 2Multi-Precision Calculator7/16/2011 Cliff McCullough 3That’s a lot of digits7/16/2011 Cliff McCullough 4Modular ArithmeticThe Division Algorithma = m b + r“Any integer a can be divided by b in such a way that the remainder is smaller than b.”(Burton, 2007, p. 17)7/16/2011 Cliff McCullough 5Examples13 = 1 * 12 + 1◦13 ≡ 1 mod 129 = 0 * 12 + 9◦9 ≡ 9 mod 127/16/2011 Cliff McCullough 6AdditionFirst express the numbers in modular formAdd the numbers and collect the termsAdjust the multiplier if needed so that the residue is positive and less than the modulus7/16/2011 Cliff McCullough 7SubtractionFirst express the numbers in modular formSubtract the numbers and collect the termsAdjust the multiplier if needed so that the residue is positive and less than the modulus7/16/2011 Cliff McCullough 8MultiplicationMultiplication is merely repeated additionAdjust the multiplier so that the residue is positive and less than the modulus7/16/2011 Cliff McCullough 9DivisionDivision is trickyInstead of c ---- = e dWe write c = d * eAsk by what number, e, can we multiply d to result in c, in modular arithmetic?7/16/2011 Cliff McCullough 10Division by Multiplicative InverseAnother way to divide is to multiply by the MMIc * d-1 = eMMI:d * d-1 ≡ 1 mod modulusAsk by what number, d-1 , can we multiply d such that the result is 1 in modular arithmetic?7/16/2011 Cliff McCullough 11Useful FunctionsEuclidean Algorithm◦Greatest Common Divisor◦Modular Multiplicative InverseModular ExponentiationChinese Remainder TheoremEuler’s Totient Function7/16/2011 Cliff McCullough 12Greatest Common DivisorCompare the smaller number to the largerFind the quotient of the two numbersMultiply the smaller by the quotient and subtractNow compare the residue with the previous smaller numberContinue until the residue is zero7/16/2011 Cliff McCullough 13GCD ExampleExample from (Euclidean algorithm, 2011)7/16/2011 Cliff McCullough 14GCD ResultsAE = 3 * CFCD = 2 * AE + CF = 2 * 3 * CF + CF = 7 * CFAB = CD + AE = 7 * CF + 3 * CF = 10 * CF7/16/2011 Cliff McCullough 15Extended Euclidean AlgorithmUse Extended Euclidean AlgorithmBasically keep track of the coefficients1. Start by writing the two numbers2. Find the quotient3. Multiply the second equation by the quotient and subtract from the first4. Repeat steps 2 and 3 until the residue is zero7/16/2011 Cliff McCullough 16Extended Euclid Example50 = 50 ( 1) + 35 ( 0)35 = 50 ( 0) + 35 ( 1), q = 115 = 50 ( 1) + 35 ( -1), q = 2 5 = 50 ( -2) + 35 ( 3), q = 3 0 = 50 ( 7) + 35 (-10)7/16/2011 Cliff McCullough 17Finding the MMI13 = 13 ( 1) + 4 ( 0) 4 = 13 ( 0) + 4 ( 1), q = 3 1 = 13 ( 1) + 4 ( -3)1 = 13 (1) + 4 (-3) + 13 (-4) + 4 (13)1 = 13 (1 - 4) + 4 (-3 + 13)1 = 13 (-3) + 4 (10)7/16/2011 Cliff McCullough 18Modular ExponentiationInitiate X = base, E = exponent, Y = 1If E is odd◦Replace Y = X * Y◦Replace E = E - 1E is not even◦Replace X = X * X◦Replace E = E ÷ 2When E = 0, Y is the answer(Garrett, 2004, p. 123) 7/16/2011 Cliff McCullough 19Exponentiation Example7/16/2011 Cliff McCullough 20E = 11 = 8 + 2 + 1Y = 38 * 32 * 31 = 6561 * 9 * 3Notes X E YInitialization 3 11 1E is odd 10 3E is even 9 5E is odd 4 27E is even 81 2E is even 6561 1E is odd 0 177147Modular Exponentiation ExampleE = 11 = 8 + 2 + 1Y = 38 * 32 * 31 = 237 * 9 * 3 mod 5277/16/2011 Cliff McCullough 21Notes X E YInitialization 3 11 1E is odd 10 3E is even 9 5E is odd 4 27E is even 81 2E is even 237 1E is odd 0 75Consider Multiplication 1111 11 x 1111 x 11---------------- -------- 1111 11 1111 + 11 1111 -------- + 1111 1001---------------- 111000017/16/2011 Cliff McCullough 22Chinese Remainder TheoremReduces calculation time by dealing with smaller numbersSome elements may be pre-calculated and used repeatedly for subsequent calculations7/16/2011 Cliff McCullough 23How To CRTPre-calculations◦Know the Factors of M◦Calculate each Mi◦Calculate MMI of each Mi mod mi◦Calculate AiPerform the operationCombine the results(Stallings, 2011, pp. p 254-257)7/16/2011 Cliff McCullough 24CRT Pre-calculationsChose m1 and m2M = m1 * m2 = 37 * 49 = 1813Calculate Mi = M ÷ miM1= 1813 ÷ 37 = 49M2 = 1813 ÷ 49 = 37Calculate Mi-1 mod miM1-1 mod m1 = 49-1 mod 37 ≡ 34M2-1 mod m2 = 37-1 mod 49 ≡ 47/16/2011 Cliff McCullough 25CRT Pre-calculations tooCalculate AiA1 = M1 * M1-1 mod M = 49 * 34 mod 1813 ≡ 1666A2 = M2 * M2-1 mod M = 37 * 4 mod 1813 ≡ 1487/16/2011 Cliff McCullough 26CRT AdditionCompute x + y = zi mod mi for each mi 973 mod 37 = 11 973 mod 49 = 42+ 678 mod 37 = 12 + 678 mod 49 = 41----------------- ----------------- z1 = 23 mod 37 z2 = 34 mod 49Combine results(x + y) mod M = (z1 * A1 + z2 * A2) mod M(973 + 678) mod 1813 = (23 * 1666 + 34 * 148) mod 1813 ≡ 16517/16/2011 Cliff McCullough 27CRT MultiplicationCompute x * y = zi mod mi for each mi 973 mod 37 = 11 973 mod 49 = 42* 678 mod 37 = 12 * 678 mod 49 = 41----------------- ----------------- z1 = 14 mod 37 z2 = 32 mod 49Combine results(x * y) mod M =