Modular Arithmetic - Home | College of Engineering and ...



The Algebra of EncryptionModular ArithmeticMuch of modern cryptography is based on modular arithmetic. We can think of modular arithmetic as a cycle. When we reach the base number or modulus, we cycle back to zero. We use modular arithmetic every day. For example, when we look at the clock we are using base 12. If the current time is 9 am and an appointment is at 1 pm, we know that the appointment is four hours away. Modular arithmetic tells us that 1-9≡4 mod 12. (Modular arithmetic, 2011)Division AlgorithmThe division algorithm roughly states “that any integer a can be “divided” by b in such a way that the remainder is smaller than b.” (Burton, 2007, p. 17) Mathematically, this can be expressed as followsa=mb+rEquation 11Where m is a multiplier and r is a residue.Example 1113=1*12+1, the multiplier is 1 and the residue is 1. Using modular arithmetic, we write 13≡1 mod 12.Example 129=0*12+9, in this case the multiplier is zero and the residue is equal to 9 or a. Using modular arithmetic, we write 9≡9 mod 12.AdditionAddition follows the same rules that we are used to from normal arithmetic with the additional step that the result is reduced by the modulus.To add two numbers a1 and a2 we first express the numbers in the form of REF _Ref298854738 \h Equation 11.a1=m1*b+r1a2=m2*b+r2Next we add and collect terms.a1+a2=m1+m2*b+(r1+r2)Note that this remains in the form of REF _Ref298854738 \h Equation 11 but does not preclude the possibility that the sum r1+r2 could be greater than the modulus, thus causing a change to the multiplier.Example 1313+9≡10 mod 12 13+9=1*12+1+0*12+9=1+0*12+1+9=1*12+10In this case, the multiplier is not affected.Example 149+9≡6 mod 129+9=0*12+9+ 0*12+9=0+0*12+9+9=0*12+18In this case, the resulting residue is greater than the modulus and should be reduced. Add and subtract the modulus, 12, and collect terms.18=0*12+18+1*12-12=0+1*12+18-12=1*12+6SubtractionModular subtraction is similar to modular addition. To subtract two numbers a1 and a2 we first express the numbers in the form of REF _Ref298854738 \h Equation 11.a1=m1*b+r1a2=m2*b+r2Next we subtract and collect terms.a1-a2=m1-m2*b+(r1-r2)Again, the result remains in the form of REF _Ref298854738 \h Equation 11 but does not preclude the possibility that the difference r1-r2 could be less than the zero. Since we generally deal with positive numbers, this causes a change to the multiplier.Example 159-13≡8 mod 12 9-13=0*12+9-1*12+1=0-1*12+9-1=-1*12+8In this case, the multiplier is not affected.Example 1613-9≡4 mod 1213-9=1*12+1- 0*12+9=1-0*12+1-9=1*12+(-8)In this case, the resulting residue is less than zero and should be adjusted. Add and subtract the modulus, 12, and collect terms.-8=1*12+-8+-1*12+12=1-1*12+-8+12=0*12+4MultiplicationMultiplication is merely repeated addition. As with addition and subtraction, the resulting residue is generally adjusted to be less than the modulus and non-negative.Example 174*13≡4 mod 12 4*13=1*12+1+1*12+1+1*12+1+1*12+1=1+1+1+1*12+1+1+1+1=4*12+4In this case, the multiplier is not affected.Example 1813*4≡4 mod 1213*4=13*0*12+4=13*0*12+13*4=0*12+52In this case, the resulting residue should be adjusted.52=4*12+4DivisionDivision is a little tricky. Normally we think of division as dividing one number into equal parts countable to another. Thus the name. However, when we stick to Integers, we don’t always get equal Integer parts.We need to think of modular division a little differently. Generally, when we divide c by d we use the following notation.cd=eEquation 12For modular division, we need to write this in a different way.c=d*e or d*e=cEquation 13If trying to divide c by d, we need to ask by what number, e, can we multiply d such that the result is congruent to c modulo the modulus?Example 1910÷2≡5 mod 13 2*5=10=0*13+10This is easy because we know we can multiply 2 by 5 and the result is 10.Example 11010÷4≡9 mod 13In this case, 4*9=36=2*13+10. That is to say, we found a number, 9, that we can multiply by 4 such that the result is congruent to 10 modulo 13. Exactly how we find the number 9 directly, without trial and error, is discussed in section REF _Ref297803443 \r \h 1.6 and REF _Ref297984544 \n \h 2.1.2.Division by Multiplicative InverseAnother way of accomplishing modular division is by using the multiplicative inverse of the divisor. Re-writing REF _Ref297802046 \h Equation 12, we get the following equation for division.c*d-1=eEquation 14But this begs the question, what is the multiplicative inverse in modular arithmetic? Remembering back to regular arithmetic, we again think of multiplicative inverse in a different way. We need to ask by what number, d-1, can we multiply d such that the result is congruent to 1 modulo the modulus? This is expressed mathematically as follows.1≡d*d-1 mod modulusEquation 15Expressed algebraically for modular arithmetic, we have the following.1=m*b+d*d-1Equation 16Where again, m is the multiplier, b is the modulus, d is the number of interest, and d-1 is the Modular Multiplicative Inverse (MMI).Example 111(4)-1≡10 mod 13 1=-3*13+4*10.Again, exactly how we find the number 10 directly, without trial and error, is discussed in section REF _Ref297984544 \n \h 2.1.2.Example 112Going back to REF _Ref297803085 \h Example 110, we get the following.10÷4=10*4-1≡10*10 mod 13=100=7*13+9≡9 mod 13, which agrees with the findings in REF _Ref297803085 \h Example 110.Useful FunctionsEuclidean AlgorithmThe Euclidean algorithm is an important part of the algebra of encryption. It is generally thought of as providing the Greatest Common Divisor (GCD) of two numbers. When the two numbers are properly chosen, the Euclidean algorithm can also be used to directly determine the Modular Multiplicative Inverse (MMI).Greatest Common Divisor“The Euclidean algorithm (also called Euclid’s algorithm) is an efficient method for computing the greatest common divisor.” “The GCD of two numbers is the largest number that divides both of them without leaving a remainder.” (Euclidean algorithm, 2011) REF _Ref297806381 \h Figure 21 reproduces an example discussed in (Euclidean algorithm, 2011). We would like to find the GCD of two numbers represented by lines AB and CD.Start by comparing the smaller number to the larger number.Find the quotient of the two numbers. In this case, the quotient refers to the greatest integer less than or equal to AB÷CD. In other words, how many times can we multiply CD and still remain smaller than or equal to AB. In the figure, this quotient is 1.Multiply the second number by the quotient and subtract from the first. In the figure, the result, or residue, is AE.Now compare the residue with the previous smaller number. In the figure, this is comparing CD and AE. Repeat the above steps until the larger number is an integral multiple of the smaller number. That is to say, there is no resulting residue. The GCD is the last residue, in this case, CF.Figure 21: Euclidean AlgorithmNow we can add up the line lengths and verify that CF is the GCD of AB and CD.AE=3*CFCD=2*AE+CF=2*3*CF+CF=7*CFAB=CD+AE=7*CF+3*CF=10*CFReferring to REF _Ref298093100 \h Figure 22, it is easy to see that CF does indeed evenly divide both AB and CD.Figure 22: Comparing the ResultsModular Multiplicative InverseBy computing the Euclidian algorithm on a number of interest and the modulus, we can directly compute the MMI of the number of interest. In these calculations, it is efficient to accumulate the quotients at each step as coefficients of the two numbers. This is often referred to as the Extended Euclidean algorithm.If we put numbers to the lines in REF _Ref297806381 \h Figure 21, for example 50 and 35, we have the following example.Example 211. Start by writing the two numbers as below.50 = 50 ( 1) + 35 ( 0)35 = 50 ( 0) + 35 ( 1)2. Find the quotient of the two numbers.q = int(50 / 35) = 13. Multiply the second equation through by the quotient and subtract from the first.50 = 50 ( 1) + 35 ( 0)35 = 50 ( 0) + 35 ( 1), q = 115 = 50 ( 1) + 35 ( -1)4. Repeat steps 2 and 3 comparing the residues until the result is 050 = 50 ( 1) + 35 ( 0)35 = 50 ( 0) + 35 ( 1), q = 115 = 50 ( 1) + 35 ( -1), q = 2 5 = 50 ( -2) + 35 ( 3), q = 3 0 = 50 ( 7) + 35 (-10)The GCD is the last residue, in this case, 5. If we work this example again using the numbers 10 and 7, we will find that the GCD is 1. If two numbers have a GCD of 1, they are said to be relatively prime or coprime. (Coprime, 2011)Now, how does this find the MMI? If we return to REF _Ref297810495 \h Example 111, we wish to find the MMI of 4 modulo 13. If we compute the Extended Euclidian algorithm of 13 and 4 we have the following.13 = 13 ( 1) + 4 ( 0) 4 = 13 ( 0) + 4 ( 1), q = 3 1 = 13 ( 1) + 4 ( -3)When searching for the MMI, we can stop when the residue is 1. Now compare our result with REF _Ref297812125 \h Equation 16. (-3) is the MMI of 4 modulo 13. We prefer to deal with non-negative numbers, so the result needs to be adjusted. We do this by adding and subtracting 13 * 4 and collecting terms.1 = 13 (1 ) + 4 (-3 ) + 13 (-4) + 4 (13)1 = 13 (1 - 4) + 4 (-3 + 13)1 = 13 ( -3) + 4 ( 10)Thus 10 is the MMI of 4 mod 13. This result agrees with our findings in REF _Ref297810495 \h Example 111.Mentioned above is that we can stop searching for the MMI when the residue is 1. This is because the next line would result in a residue of zero. When we arrive at a residue of zero but the previous line does not have a residue of 1, the number of interest and the modulus are not coprime and no MMI exists for that number of interest for that modulus. (Burton, 2007, pp. 76-77)Modular ExponentiationMany encryption schemes employ modular exponentiation. When dealing with very large numbers, such as in cryptography, efficient computing is essential. (Garrett, 2004, p. 123) describes an algorithm entitled Fast Modular Exponentiation.Initiate X = base, E = exponent, Y = 1: xe≡y mod m.If E is odd: replace Y by (X * Y) mod m and replace E = E - 1.E is now even: replace X by (X * X) mod m and replace E = E / 2.When E = 0: xe≡y mod m.X keeps the current binary power of the base number. Y is the accumulator. Note how E is parsed for its binary bit values. Starting from the least significant bit, check if the bit is 1 (if E is odd). If E is odd, accumulate the corresponding power of the base: Y = Y * X. The decrement of E simply makes the division by 2 in the next step easier.E is now even, update X to the next binary power of the base: X = X * X. Divide E by 2, that is to say, right shift so the next binary bit is in the least significant bit position.Loop to step REF _Ref297919760 \n \h 2 until E = 0.Example 22First let’s calculate 311 without a modulus.E=11=1+2+8.Y=311=31*32*38=3*9*6561=177147NotesXEYInitialization31=3111E is odd11-1=103*1=3E is even32=910÷2=5E is odd5-1=49*3=27E is even34=814÷2=2E is even38=65612÷2=1E is odd1-1=06561*9*3=177147Example 23Now let’s calculate 311 mod 527Y=311=31*32*38=3*9*237 mod 527=75 mod 527NotesXEYInitialization31=3111E is odd11-1=103*1 mod 527=3E is even32 mod 527=910÷2=5E is odd5-1=49*3=27 mod 527E is even34 mod 527=814÷2=2E is even38 mod 527=2372÷2=1E is odd1-1=0237*9*3 mod 527=75You can verify that 177,147 = 75 mod 527.Notice that everything happens the same with a modulus as without a modulus. The only difference is in the size of the numbers - the calculation results are reduced modulo 527.Also notice the significant role of multiplication in this algorithm. We multiply X*X for each exponent bit position. We multiply X*Y when the exponent’s least significant bit is 1. In REF _Ref297980940 \h Example 22 we dealt with larger numbers. In REF _Ref297980972 \h Example 23 the numbers were limited by the modulus and remained smaller.Consider multiplying two 4 digit binary numbers and two 2 digit binary numbers. 1111 x 1111----------------- 1111 1111 1111 + 1111----------------- 11100001 11 x 11----------------- 11 + 11----------------- 1001The 4 digit multiplication involved the addition of 16 bits. The 2 digit multiplication involved the addition of only 4 bits. Since the size of numbers cryptography deals with are usually larger than a computer’s arithmetic logic unit can deal with, special Big Integer computational packages such as Multiple Precision Integers and Rationals (MPIR) CITATION MPI11 \l 1033 (MPIR home page) or Gnu Multiple Precision (GMP) CITATION The11 \l 1033 (The GNU Multiple Precision Arithmetic Library) are usually employed. The smaller the modulus, the smaller the numbers we deal with, and the less time involved in multiplying.Chinese Remainder Theorem (CRT)Chinese Remainder Theorem is frequently used in cryptography to reduce the calculation time inherent in calculating with large numbers. This time reduction is accomplished by doing a few extra calculations, but with much smaller numbers. (Chinese remainder theorem, 2011) Also, a significant part of the calculations may be done once, in advance, and then used for subsequent calculations.This discussion follows CITATION Sta11 \p "p 254-257" \l 1033 (Stallings, 2011, pp. p 254-257). The example will use a modulus with four factors.Pre-calculationsIdentify the Factors of MChoose m1, m2, m3, and m4. The numbers must be coprime.m1=37m2=49= 72m3=55=5*11m4=64=26Notice that m2 and m4 are powers of prime numbers and m3 is composite. Only m1 is truly prime in this example. The only requirement is that the chosen factors of M be coprime with respect to each other.M=m1*m2*m3*m4=37*49*55*64=6,381,760Calculate MiCalculate Mi=M÷mi for each mi.M1=M÷m1=6,381,760 ÷37=172,480M2=M÷m2=6,381,760 ÷49=130,240M3=M÷m2=6,381,760 ÷55=116,032M4=M÷m4=6,381,760 ÷64=99,715Calculate Mi-1 mod miUse the Extended Euclidean Algorithm to calculate Mi-1 mod mi for each mi.M1-1 mod m1=172,480-1 mod 37≡29M2-1 mod m2=130,240-1 mod 49≡24M3-1 mod m3=116,032-1 mod 55≡3M4-1 mod m4=99,715-1 mod 64≡43Calculate AiFor convenience, define Ai=Mi*Mi-1 mod M for each mi.A1=M1*M1-1 mod M=172,480*29 mod 6,381,760≡5,001,920A2=M2*M2-1 mod M=130,240*24 mod 6,381,760≡3,125,760A3=M3*M3-1 mod M=116,032*3 mod 6,381,760≡348,096A4=M4*M4-1 mod M=99,715*43 mod 6,381,760≡4,287,745AdditionTo add two numbers, complete the addition for each mi, then combine the results.As an example, we will add 735,839 and 826,277 mod M. Start by computing the residue for each factor.x=735,839x1=x mod m1=735,839 mod 37=20x2=x mod m2=735,839 mod 49=6x3=x mod m3=735,839 mod 55=49x4=x mod m4=735,839 mod 64=31y=826,277y1=y mod m1=826,277 mod 37=30y2=y mod m2=826,277 mod 49=39y3=y mod m3=826,277 mod 55=12y4=y mod m4=826,277 mod 64=37Add for each miCompute x+y=zi mod mi for each mi.z1=x1+y1=20+30=50≡13 mod 37z2=x2+y2=6+39=45≡45 mod 49z3=x3+y3=49+12=61≡6 mod 55z4=x4+y4=31+37=68≡4 mod 64Combine the resultsFind the result of x+y mod M=(z1*A1+z2*A2+z3*A3+z4*A4) mod M735,839+826,277 mod 6,381,760=13*5,001,920+45*3,125,760+6*348,096+4*4,287,745 mod 6,381,760≡1,562,116MultiplicationTo multiply two numbers, complete the multiplication for each mi, then combine the results.If we use the same x and y values as for addition, we can use the same residues for each factor.Multiply for each miCompute x*y=zi mod mi for each mi.z1=x1*y1=20*30=600≡8 mod 37z2=x2*y2=6*39=234≡38 mod 49z3=x3*y3=49*12=588≡38 mod 55z4=x4*y4=31*37=1147≡59 mod 64Combine the resultsFind the result of x*y mod M=(z1*A1+z2*A2+z3*A3+z4*A4) mod M735,839*826,277 mod 6,381,760=8*5,001,920+38*3,125,760+38*348,096+59*4,287,745 mod 6381760≡3,802,683Euler’s Totient FunctionEuler’s totient function, Φ(n), identifies the number of integers, less than n, that are relatively prime to n. A good treatment of Euler’s Totient function can be found in CITATION Bur07 \p 131-135 \l 1033 (Burton, 2007, pp. 131-135).(Stallings, 2011, pp. 249-250) presents Euler’s totient function as Φp=p-1 for prime p. This is correct, but not good for a general definition of the function. CITATION Bur07 \p 131-135 \l 1033 (Burton, 2007, pp. 131-135) gives a more versatile definition as Φpk=pk-pk-1. It is easy to see that this version degenerates to the previous version in the case of k=1.To determine the totient of a composite number, we must know the prime factors of the number. Given n=pi*qj, Φn=Φpi*Φqj=pi-pi-1*(qj-qj-1) CITATION Bur07 \p 131-135 \l 1033 (Burton, 2007, pp. 131-135). Again, if i and j=1, then the equation degenerates to Φn=Φp*Φq=p-1*(q-1) as described by (Stallings, 2011, pp. 249-250).Example 24 To calculate Φ(21), the first form is adequate. First we must know the prime factors of 21, namely 3 and 7.Φ21=3-1*7-1=2*6=12Therefore, the number of integers less than 21 relatively prime to 21 should count to 12.1, 2, 4, 5, 8, 10, 11, 13, 16, 17, 19, 20 are the 12 numbers less than 21 that are relatively prime to 21.Example 25To calculate Φ(20), the second form of the totient function is required. The prime factors of 20 are 22 and 5.Φ20=22-21*51-50=4-2*5-1=2*4=8The 8 integers less than 20 relatively prime to 20 are 1, 3, 7, 9, 11, 13, 17, 19.Exponentiation and Chinese Remainder TheoremIn section REF _Ref298847479 \n \h 2.3 we looked at addition and multiplication using CRT. We would like to take advantage of the CRT and reduce the exponent. Notice that reducing the exponent by the modulus does not result in congruence.be=bmnn+rn?brn mod nwhere b is the base, mn is the multiplier, and rn is the residue.To demonstrate this, lete=131n=17b=3e=131=mnn+rn=7*17+12be=3131=10 mod 17brn=312=4 mod 17be?brn mod nTo reduce the exponent correctly, we must employ Euler’s theorem. Euler’s theorem states that if n≥1 and gcda,n=1, then aΦ(n)≡1 mod n. CITATION Bur07 \p 137 \l 1033 (Burton, 2007, p. 137)be=bmΦΦ(n)+rΦ≡brΦ mod nwhere b is the base, mΦ is the multiplier, and rΦ is the residue.To demonstrate this, lete=131n=17, Φn=16b=3e=131=mΦΦ(n)+rΦ=8*16+3be=3131=10 mod 17brΦ=33=10 mod 17be≡brΦ mod nWe can always use the full exponent when conducting the calculations for each CRT modulus. But to reduce the exponent, we must know Φ(n) which requires we know the factors of n if n is not prime. Public Key Cryptography - RSAEuler’s theorem is the heart of the RSA encryption and decryption method. CITATION RSA11 \l 1033 (RSA, 2011).If we choose two prime numbers p and q we can form n=p*q and determine Φ(n). If we then choose an encryption exponent e so that gdce, Φn=1, we can find a decryption exponent d such that d*e≡1 mod Φ(n). The exponent d is merely the MMI of e mod Φ(n), and we know from section REF _Ref297984544 \r \h 2.1.2 how to find d. Note that d*e=m*Φn+1 for some multiplier m.Now take a message expressed as a number M. Calculate the encrypted message by using the encryption exponent.C=Me mod nTo decrypt, use the decryption exponent. Calculate Cd mod n=M.Cd=(Me)d=Mm*Φn+1=Mm*Φn*M=(MΦn)m*MTaking note of Euler’s theorem, if the decryption calculations are made modulo n, we haveCd=(1)m*M mod n=MThus we have successfully decrypted the message, assuming gcdM,n=1 to satisfy the requirements of Euler’s theorem. “In the unlikely event that M and n are not relatively prime, a similar argument establishes that [Cd]≡M mod p and [Cd]≡M mod q, which then yields the desired congruence [Cd]≡M mod n. We omit the details.” CITATION Bur07 \p 204 \l 1033 (Burton, 2007, p. 204)RSA involves calculating modular exponentials. The example uses normal encryption and CRT decryption. Note that CRT only benefits decryption because the factors of the modulus must be known and they are part of the private key.Let:p=17q=31e=11message: M=3calculate n=p*q=17*31=527calculate Φn=p-1*q-1=16*30=480calculate d=e-1 mod Φn≡131CRT Pre-calculationsP=n÷p=31P-1 mod p≡11Ap=P*P-1 mod n=31*11 mod 527≡341Q=n÷q=17Q-1 mod q≡11Aq=Q*Q-1 mod n=17*11 mod 527≡187dp=d mod Φp=131 mod 16≡3dq=d mod Φq=131 mod 30≡11See section REF _Ref298848417 \n \h 3 regarding how to reduce the exponent d into dp and dq.EncryptC=Me mod n=311 mod 527≡75 (See REF _Ref297980972 \h Example 23.)DecryptNote the use of dp and dq in place of the normal decrypt exponent.Mp=Cdp mod p=753 mod 17 =73 mod 17≡3 Mq=Cdq mod q=7511 mod 31 =1311 mod 31≡3 Combine the resultsM=Mp*Ap+Mq*Aq mod n=3*341+3*187 mod 527≡3ConclusionDecryption is accomplished using smaller exponents and smaller moduli. Multiplication is a large part of calculating modular exponentials. When computing many exponentials using the same private key, time savings becomes significant.How to Share a Secret(Shamir, November, 1979) describes how to share secret information such that the holders of a share cannot individually obtain the secret. Only if a certain minimum number of share holders collaborate can the secret information be identified.A simple description of this method is to use a curve described by a polynomial function.fx=atxt+at-1xt-1?a1x+a0Equation 51Typically, a0 is the secret information, for example a secret key, and the other t coefficients in the polynomial may be chosen at random. If two or more elements comprise the secret key, such as p, q, and d , necessary for CRT decryption of RSA, then more coefficients may be set and the remainder chosen at random.Basic algebra tells us that when we have t+1 unknowns - the t+1 coefficients, we need to know t+1 points on the curve to identify all of the coefficients. We really only want the one coefficient, a0, but even that cannot be determined without the required minimum number of points from the curve.Points on the curve - x and f(x) pairs, are the secret shares given to the trusted authorities. Many more than t+1 secret shares may be given out. But, only if a minimum of t+1 trusted authorities agree to provide their secret share and collaborate, can the secret information be identified. The secret information - coefficient(s) of the polynomial, may be identified by any linear algebra method for solving a system of simultaneous equations.The x values may be as simple as indexes, incremented between one share holder to the next. Only the value of f(x) must be held secret.Paillier CryptographyThe cryptographic systems proposed by (Paillier, 1999) involve polynomial expansion of exponentiation. Paillier proposed three systems, one will be discussed here. It is similar to RSA cryptography.Carmichael FunctionIn order to understand the algebra of Paillier cryptography, we need to understand the Carmichael function. The Carmichael function, λ(n), is similar to Euler’s totient function Φ(n). (Paillier, 1999, p. 2)λn=lcm(p-1, q-1)Equation 61where n=pq, p and q are distinct primes, and lcm stands for Least Common Multiple.The Carmichael function also has some useful properties for Paillier cryptography. For any integer w that is coprime with n:wλ≡1 mod nwnλ≡1 mod n2Equation 62Which implies there exists some integer a and b such thatwλ=an+1wλn=bn2+1Equation 63PreliminariesChoose two safe prime numbers p and q, form n=p*q, and determine λ=lcm(p-1, q-1). Safe prime numbers are of the form 2p+1, where p is also a prime. CITATION Saf10 \l 1033 (Safe prime, 2010)Define the functionLu=u-1nEquation 64Note: that u is usually an exponential mod n2. The notation used is a little awkward because only the exponential should be calculated mod n2. The division by n cannot be accomplished mod n2 because n has no MMI mod n2. The numerator should be a multiple of n, and the “normal” division should result in an integer with no residue.Choose a generator value g such thatgcdLgλ mod n2, n=1Equation 65Note: See section REF _Ref298926399 \n \h 6.12 regarding choosing values of g.The public key is (g, n). The private key is λ.EncryptThe plaintext message is m<n. Choose a random number r<n. Calculate the encrypted messagec=gmrn mod n2Equation 66DecryptPlaintext m=L(cλ mod n2)L(gλ mod n2) mod nEquation 67ExplanationThe Generator gStarting from the Carmichael function REF _Ref298262866 \h Equation 63.gλ=1+angλx=1+anxEquation 68If we use binomial expansion of the polynomial, we get CITATION Bin11 \l 1033 (Binomial theorem, 2011)(1+an)x=1x+x*1x-1*an1+x2*1x-2*n2+?wherexi=x!i!x-i!When we reduce modulo n2, all of the polynomial terms of n2 and higher drop out. We are left withgλx=(1+an)x=(1+xan) mod n2Equation 69The Decrypt NumeratorLcλ mod n2=cλ-1n mod n2=(gmrn)λ-1n mod n2=gmλrnλ-1n mod n2Applying REF _Ref298070050 \h Equation 62 to rnλ.Lcλ mod n2≡gmλ1-1n mod n2Applying REF _Ref298070653 \h Equation 69 to gmλLcλ mod n2≡1+man-1n mod n2=mann mod n2=ma mod n2Equation 610Note that we must divide by n using normal division. n has no multiplicative inverse mod n2.The Decrypt DenominatorLgλ mod n2=gλ-1n mod n2=1+an-1n mod n2=a mod n2Equation 611Again, we must divide by n using normal division.The DecryptCombining REF _Ref298071365 \h Equation 610 and REF _Ref298071372 \h Equation 611 into REF _Ref298071380 \h Equation 67, we getm=L(cλ mod n2)L(gλ mod n2) mod n=ma mod n2a mod n2 mod nSee section REF _Ref298927605 \n \h 6.11 concerning pre-calculations. The decrypt equation can be written asm=Lcλ mod n2*μ mod nwhereμ=gλ-1n mod n2-1 mod nPaillier Cryptography ExamplePreliminariesLetp=23q=59n=p*q=23*59=1357n2=1,841,449λ=lcmp-1, q-1=p-1(q-1)gcdp-1, q-1=22*582=638Choose gg=71Check g (see section REF _Ref298926399 \n \h 6.12.)gcdg,n=1g≠an+1 for some integer a.Verify ggλ mod n2=71638=521,089Lgλ mod n2=gλ-1nmod n2=521,089-11357mod 1,841,449=384gcdLgλ mod n2, n=gcd384, 1357=1Pre-calculate μ (See section REF _Ref298927605 \n \h 6.11.)μ=Lgλ mod n2-1 mod n=384-1 mod n=887EncryptLetm=1025r=1019c=gmrn mod n2=711025*10191357mod 1,841,449=1,593,818DecryptNumerator:Lcλ mod n2=cλ-1nmod n2=1,593,818638-11357mod 1,841,449=70Plaintext:m=Lcλ mod n2*μ mod n=70*887 mod 1357=1025BlindingCryptographic blinding allows for a message to be multiplied by a specially treated random number, while still allowing the message to be decrypted without knowledge of the random number. (Blinding (cryptography), 2011)Due to the properties of Paillier cryptography noted in REF _Ref298070050 \h Equation 62, any succession of blinding factors may be applied to the ciphertext without affecting the successful decryption.To see this, apply a succession of k blinding factors to the same message.c=gm*r1nr2n?rkn mod n2=gm*rn mod n2where r=kri. r is still a random number and does not affect the successful decryption of the message.Blinding ExampleWe use the ciphertext from the example in section REF _Ref298853249 \n \h 6.6 and chose another random number.c1=1,593,818r2=951c2=c1r2n mod n2=1,593,818*9511357 mod 1,841,449=1,587,825DecryptNumerator:Lcλ mod n2=cλ-1nmod n2=1,587,825638-11357mod 1,841,449=70As we saw in the explanation in section REF _Ref298853722 \n \h 6.5, the decrypt numerator is unaffected by the blinding of the added random number.Additive Homomorphic PropertiesPaillier cryptography includes an interesting homomorphic property in that the multiplication of two ciphertexts is equivalent to the addition of the respective plaintexts. (Paillier, 1999, p. 13)To see this, start with two messages m1 and m2 and encrypt.c1=gm1r1n mod n2c2=gm2r2n mod n2Now multiply the two ciphertexts.c1*c2=gm1r1n*gm2r2n mod n2=gm1gm2*r1nr2n mod n2=gm1+m2*(r1r2)n mod n2=gm3*r3n mod n2where m3=m1+m2 and r3=r1*r2. r3 is a random number, and the product c1*c2 will correctly decrypt as m1+m2.Homomorphic ExampleWe use the ciphertext from the example in section REF _Ref298853249 \n \h 6.6 and section REF _Ref298854097 \n \h 6.8. These two ciphertext represent the same plaintext, so the expected result is that the original message will be doubled.c3=c1*c2=1,593,818*1,587,825 mod 1,841,449=705,150DecryptNumerator:Lcλ mod n2=cλ-1nmod n2=705,150638-11357mod 1,841,449=140Plaintext:m=Lcλ mod n2*μ mod n=140*887 mod 1357=693Which is as expected since 2*1025 mod 1357=693.Pre-calculationsSome elements of Paillier cryptography can be pre-calculated.DecryptionThe decrypt denominator is actually calculated when g is verified. The only additional pre-calculation is to find the MMI of the denominator.μ=gλ-1n mod n2-1 mod nEquation 612Decryption then becomesm=Lcλ mod n2*μ mod nEquation 613Determine λBecause p and q are safe primes, we have the following determination for λ.p=2p'+1q=2q'+1where p' and q' are also primes.This leads to the following pre-calculation for λ.λ=lcmp-1, q-1=p-1(q-1)gcd?(p-1, q-1)=2p'(2q')gcd?(2p', 2q')=4p'q'2=2p'q'Equation 614ObservationsChoosing g with a common factor to nThe choosing of g, REF _Ref298263105 \h Equation 65, allows a vulnerability. If g shares a factor with n, the division of the numerator of L(gλ mod n2) by the denominator, n, does not always yield an integer. CITATION Pai99 \l 1033 (Paillier, 1999) never discusses that the division result should be verified to be an integer. If this goes un-noticed, and the result is truncated, the equality of REF _Ref298263105 \h Equation 65 may hold and the value of g will be accepted.Example 61p=7=2*3+1, p'=3q=11=2*5+1, q'=5n=p*q=77n2=5929λ=2p'q'=2*3*5=30g=35=5*7gcdg, n=7Lgλ mod n2=gλmod n2-1n=3530 mod 5929-177=2597-177=33.7gcdLgλ mod n2, n=gcd33, 77=11Example 62Same as REF _Ref299395024 \h Example 61 except:g=22=2*11gcdg,n=11Lgλ mod n2=gλmod n2-1n=2230 mod 5929-177=484-177=6.27gcdLgλ mod n2, n=gcd6, 77=1In REF _Ref299395024 \h Example 61, the choice of g is rejected. In REF _Ref299395288 \h Example 62, the choice of g is accepted.The public key is (g, n). If g shares a factor with n, the astute adversary would be able to employ the Euclid algorithm to factor n and thereby find the secret key λ.Choosing g without BlindingIf one should choose g=1+an, for some integer a, blinding is in fact necessary. Consider encryption REF _Ref298073388 \h Equation 66 without the blinding factor rn.c=gm=1+anmFollowing the same process as the derivation of REF _Ref298070653 \h Equation 69, we arrive atc=(1+an)m=1+man mod n2Because (g, n) is the public key, the value of a is known publicly. Thus m can be easily calculated from c. Thus Blinding is necessary if g is chosen such that g=1+an.Works Cited BIBLIOGRAPHY Binomial theorem. (2011, June 21). Retrieved July 10, 2011, from Wikipedia: (cryptography). (2011, June 3). Retrieved July 10, 2011, from Wikipedia: (cryptography)Burton, D. M. (2007). Elementary Number Theory, Sixth Edition. New York, New York 10020: McGraw-Hill Higher Education.Chinese remainder theorem. (2011, July 2). Retrieved July 7, 2011, from Wikipedia: . (2011, June 25). Retrieved July 7, 2011, from Wikipedia: algorithm. (2011, June 30). Retrieved July 7, 2011, from Wikipedia: , P. (2004). The Mathematics of Coding Theory. Upper Saddle River, New Jersey: Pearson Prentice Hall.Modular arithmetic. (2011, July 5). Retrieved July 7, 2011, from Wikipedia: home page. (n.d.). Retrieved July 9, 2011, from MPIR: , P. (1999). Public-Key Cryptosystems Based on Composite Degree Residuosity Clases. Advances in Cryptology - Eurocrypt '99 , pp. 223-238.RSA. (2011, July 8). Retrieved July 8, 2011, from Wikipedia: prime. (2010, August 24). Retrieved July 9, 2011, from Wikipedia: , A. (November, 1979). How to Share a Secret. Communications of the ACM , 612-613.Stallings, W. (2011). Cryptography and Network Security, Principles and Practice, Fifth Edition. Prentice Hall.The GNU Multiple Precision Arithmetic Library. (n.d.). Retrieved July 9, 2011, from GNU: ................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download