Chapter 5. Other Bases of Cryptosystems

5.1 Exponentiation in Quadratic Fields

The framework presented in Section 2.2 for the construction of public-key crypto­systems is very general. Indeed, the area or subject matter of the underlying problem is not specified in any way. Any one-way street could be worth a try, and many streets have actually been tried. By now there exist numerous public-key cryptosystems, based on quite diverse concepts.

The purpose of this chapter is to give an idea of various types of existing public-key cryptosystems. The presentation is by no means intended to be exhaustive - only few systems will be discussed. No attempt has been made to select the "best" systems but only to present material that might inspire research towards public-key cryptosystems not dangerously depending on the difficulty of some specific number-theoretic problem.

As we have observed in many contexts, one can very seldom obtain mathemat­ical results concerning the quality of a cryptosystem; any notions of security are usually based on experience. Consequently, a comparison between different sys­tems and a selection of some best systems is in most cases futile. Many cryptosys­tems have been motivated in the literature by simply stating that the cryptanalysis leads to such and such difficult problem. This is not sufficient because the problem might turn out to be easier than expected. In general it is also not known that a solution of the underlying problem is actually needed for cryptanalysis; a clever bypass might be found.

In RSA the underlying problem is the factoring of the product of two primes. As we have pointed out, the complexity of this problem is not known. It is also not known whether a bypass exists for cryptanalysis. The following cryptosystem, due to Williams [Wil], seems to possess all the advantages of RSA. Moreover, one can actually prove that any method of breaking the system by preprocessing leads to the factoring of the modulus. Thus, cryptanalysis by preprocessing is equivalent to factoring. On the other hand, the setup "chosen cryptotext" is always successful in cryptanalysis. If the system is used, this setup should not be possible for an eavesdropper.

Encryption and decryption are as fast in the system of Williams as in RSA. On the other hand, the details of the former system are much harder to describe. Instead of ordinary modular exponentiation as in RSA, numbers of the form a + b^fc are now raised to powers modulo n. Here a, b and c are integers but the

square root can be irrational. However, it is not necessary to compute the value of the square root. In what follows, all details will be presented without using the terminology of quadratic fields. Consider numbers of the form

a = a + by/c ,

where a, b, c are integers. Here y/c is understood formally as a number whose square equals c. If c remains fixed then numbers a can be viewed as pairs (a, b), with the following definition of addition and multiplication:

a, + a₂ = (a,, b_t) + (a₂, b₂) = + a₂, b_t + b₂), (a,,f>,)-(a₂, b₂) = (a^ + cb^b^ a_lb₂ + b_ta₂).

The conjugate of a number a is defined by

a = a — by/c .

The functions X_t and Y_hi = 0,1,2,..., will be useful in the sequel. By definition,

*,.(«) = XJa, b) = (a¹' + a')/2 ,

r_f(a) = Y_t(a, b) = b(a' - «')/(a - a) = (a' - .

(The last expression is intended only to aid intuition. Since the functions are defined for pairs (a, b), c should not appear.) It follows that powers of a and a can be expressed in terms of the functions:

a'' = ^(a) + Y^^fc , a¹ = *,(«) - Y,(a)y/i .

Clearly the numbers X,(a) and y,(a) are integers. Assume now that the equation

a² -cb² = 1

is satisfied and consider a and a as defined above. Then aa = 1 and

Xf - cYf = 1 , where we have omitted the argument a. Moreover, for j > i,

X_j+j = 2XjXj — Xj_i, Y_i+j = 2Xj Yj — Yj_i . From these equations and the further equations

X_i+j = X_iX_j + cY_iY_j, Yi+j = Y/Xj + X_t Yj,

we get the recursion formulas

X_2i = Xf + cYf = 2Xf - 1 ,

Y_2i = 2X_iY_i,

X_2i+1 = 2XjX_i+i — X_i ,

Y_2i +1 = 2Xj Y₍ + j — Y_l .

These formulas lead to a fast evaluation of A", and Y_i in an obvious fashion. Since X₀ = 1 and X_t = a, it also follows that X,(a) does not depend on b. Congruences are defined in the natural way:

^ai + \T^C = ^a2 ⁺ b_2>fc (mod ri)

means that both a_l = a₂ (mod n) and b₁ =b₂ (mod n).

If instead of the equation a² — cb² = 1 we assume that the congruence

(*) a² — cb² = 1 (mod n)

is valid, then the recursion formulas above must be replaced by the corresponding congruences modulo n.

The following lemma is fundamental for the cryptosystem. The lemma is the counterpart of Euler's Theorem in RSA and serves the purpose of making encryp­tion and decryption procedures inverses of each other. The proof of the lemma consists of straightforward calculations and is omitted here. An interested reader may consult [Wil].

Lemma 5.1. Assume that n is the product of two odd primes p and q, and that a, b, c are integers satisfying the congruence (*) and, moreover, the Legendre symbols

and £, = satisfy the congruences

i (mod 4) for i = p and i = q .

Assume further that (cb,n) = 1 and that the Jacobi symbol ( ^{a +} ' ' ) equals 1. Denote

m = (p- e_p)(q - £,)/4

and assume that e and d satisfy the congruence

ed = (m + l)/2 (mod m).

Under these assumptions

0L^2ed = ± a (mod n),

where a = a + b _x/c.

We are now in the position to present the details of the public-key cryptosystem due to Williams. The discussion will consist of three parts: system design, encryp­tion and decryption. An example of Jarkko Kari will be used as an illustration.

System Design. First two large primes p and q are chosen and their product n is computed. Then a number c is chosen such that the Legendre symbols e_p and e_q satisfy the congruences mentioned in Lemma 5.1. Observe that c can be found very rapidly by trial because approximately one number in four satisfies these congruen­ces. Next a number s is determined (by trial) such that the Jacobi symbol satisfies

= - 1

(and (s, n) =1). The number m is defined as in Lemma 5.1, a number d with (d, m) = 1 is chosen, as well as a number e satisfying the congruence in Lemma 5.1.

The numbers n, e, c, s are publicized, whereas the numbers p, q, m, d are kept secret.

As an example, let p = 11 and <7=13, implying n = 143. Because

Aj = 1 = - 11 and ^ ₌ _ i = _ 13 _{(mod 4)},

we may choose c = 5. We may also choose s = 2 because

- 1\ ( - 1

11 M 13 =

We now obtain m = 10-14/4 = 35. Because 23-16 = 18 (mod 35), we may finally choose the encryption and decryption exponents e = 23 and d = 16.

Encryption. Plaintexts are numbers w with 0 < w < n. (If necessary, the plaintext is first divided into blocks such that this condition concerning the size of the plaintext can be met.) Now w is first encoded as a number a of the form considered above and then encrypted by raising a to the power e modulo n. We consider first the encoding.

We denote

f>! = 0 and y = w + <Jc fc, = 1 and y = (w + _N/c)(s + *Jc),

/ w* — c \

depending on whether the Jacobi symbol I------------------ J has the value + 1 or — 1,

respectively. (The case of the Jacobi symbol being equal to 0 is so unlikely that we do not consider it.) In both cases

In the first case this is obvious and follows, in the second case, by the choice of s.

Arithmetic will be carried out modulo n. As before, the inverse x~¹ denotes an integer satisfying the congruence xx~¹ = 1 (mod n). This notation is used also if x is of the form a + by/c; then x"¹ is of the same form. For convenience we sometimes denote xy~¹ instead of x/y. The notation (x,modn) is extended to concern
numbers of the form x = a + b^/c. Thus,

(a + b^/c, mod n) = (a, mod n) + (b, mod n

The encoding is completed by defining a = y/y. Thus, writing a in the form a = a + b^/c, we have in the first case (where ft, = 0)

<x = (w² + c)/(w² - c) + (2w/(w² - c))yjc (mod n).

In the second case (where ft, = 1) we have a = a + b^fc (mod ri) with

a = ((w² + c)(s² + c) + 4c5w)/(w² - c)(s² - c)

and

ft = (2s(w² + c) + 2w(s² + c))/(w² - c)(s² - c).

The definition a = y/y guarantees that in both cases

oca = a² — eft² = 1 (mod n)

and, hence, (*) holds. This can, of course, be verified also by a straightforward calculation. We infer also

in both cases that 2(a + 1) = 2((a + a)/2 + 1) = y/y + y/y + 2 = (y + y)²/yy (mod n),

which means that the Jacobi symbol ⁺ ^^ equals 1, as required in Lemma 5.1.

Having encoded the plaintext w as a = a + b^fc, we now encrypt by raising a to the power e modulo n. As seen before, the result can be expressed in terms of X_e and Y_e. The latter can be computed rapidly using the recursion formulas. Denote

E = (X_e(a)Y_e(a)-\ mod n) .

The cryptotext is the triple (£, ft,, ft₂), where ft, was defined above and b₂ equals 0 or 1, depending on whether a is even or odd.

The number a^2e would give more direct information for decryption. However, as seen below, it can be immediately computed from the information given. The bits ft, and b₂ are needed in order to make the result of the decryption unique. Without them, in general, four different plaintexts would result.

Let us go back to our example. Take the plaintext w = 21. Because

143 J \11/ V13 we have ft, = 0, y = 21 + y/5 and

₌ 21^/5 ₌ 446 ₊ 42^5 _g 17 + 42^5 ^ _{? +} ^ 21 _. A 436 7

21 — y/5

= 125 + 6_V^5 (mod 143).

The algorithms for computing the Jacobi symbol and (w² — c)^-1 can also be combined into a single algorithm.

Since 125 is odd, we obtain b₂ = 1. To compute -X"₂₃(a)^and Y₂₃(a), ^{we now use} the recursion formulas, for instance, as follows.

*,(«)= 125, y,(a)s 6,

A-₂(a) = 75, y₂(a) = 70 ,

X₃(a) ee 35 , Y₃{a) = 48 ,

*₅(a) s 120 , y₅(a) = 44 ,

*₆(a) s 18 , y₆(a) = 71 ,

X_u(a) = 48, ^nW = 17 ,

X_l2(a) = 75 , r_l2(a) = 125 ,

X₂₃(a) = 68, Y₂₃(X) = 125 .

Hence, we obtain

£ = 68 ■ 125"¹ = 68 • 135 = 28 (mod 143). Consequently, the cryptotext is the triple (28, 0, 1).

Decryption. Using the first component £ of the cryptotext, the receiver may compute the number ot^2e:

ss «²7(««r = «7«* = (*» + Y_e{*)Jc)l{X_e(a.) - Y_e(a)V~^c) = (£ + y/c)/(E -yfc) = (£² + c)/(£² - c) + (2£/(£² - c))J~c (mod n).

Observe that this computation can be made also by a cryptanalyst who intercepted the cryptotext. However, trapdoor information is needed in the following computation:

= X_2ed(a) + Y_2ed(a)J~c = X_d(<x^2e) + Y_d(ot^2e)^/~c ,

where the X_d- and J^-values can be computed by the recursion formulas because oc^2€ is known. Now all assumptions of Lemma 5.1 are satisfied and, consequently,

_x2ed =_±ai (_m0(J „) .

The last component b₂ of the cryptotext tells which of the signs of a is the correct one. Thus, a has been computed and the plaintext w is now obtained from a and b_t (the second component of the cryptotext) as follows. Denote

~ W - ^)/(s + Jc) ifft_t = l

a' EE (w + Vc)/(w - J~c) (mod n), w = ((a' + l)/(a' - 1 ))y/c (mod n).

Returning again to the numerical example, we use first E to obtain ot^2e: a.^2e = (28² + 5)/(28² - 5) + (2-28/(28² - 5)),/5 = 95 + 126^5 (mod 143). Recall that d = 16. Therefore, we compute

X₁(u²') = 95, r,(«^2,)5l26, X₂(a^2c) = 31 , Y₂(a^2e) = 59 , X₄(<x^2e) s 62 , r₄(a^2c) = 83 , X₈(a²*) = 108 , Y₈(tx^2e) = 139 ,

X₁₆(<x²°)= 18, 7₁₆(«^2c)= 137.

Consequently, 18 + 137^/5 = ± a (mod 143). Since b₂ = 1, a must be odd and, hence,

a = - (18 + 137^5) = 125 + 6^5 (mod 143).

Using the second component b^= 0 of the cryptotext, we infer that a = a' and, therefore,

w = (126 + 6_V/5)(124 + 6^5)" ^ly/5 = (126 + 6_n/5)(124 - 6y5)(124² - S^²)"¹^ = 83-38"¹ s 21 (mod 143).

Thus w = 21, which was the original plaintext.

A reader who has worked through the details will surely agree that the cryptosystem of Williams is much more difficult to explain than RSA! However, this does not imply that encryption and decryption have greater time complexity than in RSA. We have here also the additional advantage that cryptanalysis by preprocessing is provably equivalent to factoring.

Cryptanalysis Versus Factoring. If we have found p or q, we can immediately compute m and d. Conversely, assume that a cryptanalyst has somehow found a decryption algorithm. The algorithm can be used to factor n as follows. First a number x with

is chosen by trial. Then x is encrypted but the process is begun by selecting f>, = 0 and y = x + yfc. Thus, the false value + 1 is used for the Jacobi symbol on purpose. Let (£, 0, b₂) be the resulting cryptotext. The cryptanalyst now applies the algorithm to find the corresponding plaintext w. However, w is not the same as x because the encryption process started by cheating. In fact, a fairly straightfor­ward calculation shows that (x — w, n) equals p or q. (Details can be found in [Wil].) This means that the cryptanalyst is able to factor n. The situation is analogous to knowing two distinct square roots modulo n.

Let us do this in our example. Choose x = 138. Then (**) will be satisfied. Cheat by choosing = 0 and y = 138 + y/s. Hence,

a = y/y = 73 + 7175 . Since 73 is odd, we obtain b₂ = 1. We compute next:

which yields the cryptotext (28,0, 1). It was decrypted already above with the result w = 21. This leads to the factorization of n because

(x -w,n) = (117, 143) = 13 .

The discussion shows also that if the cryptanalyst is able to apply the setup "chosen cryptotext" (even for one chosen cryptotext), the system is immediately broken.

Date: 2015-02-16; view: 627