Evaluation Report of HIME(R), CRYPTREC, IPA, 2002.

Evaluation Report of HIME(R)

July 19th, 2002
Abstract
In this report we evaluate the HIME(R), which is the public-key cryptosystem developed by HITACHI, Ltd. In section 1 we estimate the security levelof the key size for the composite numbers p2 q and p3 q that are recommended
in the specification of HIME(R). In section 2 we evaluate the correctness ofthe security proof described in the self-evaluation of HIME(R). In section
3 we compare the security and the plaintext size of HIME(R), RSA-OAEP,RSA-OAEP+, Rabin-SAEP, and Rabin-SAEP+. In section 4 we estimate thecomparison between HIME(R) primitive, RSA primitive, Rabin primitive, and
RSA-type primitive modulo pd q on their efficiency.

1

Selecting the Size of the Modulus pdq

HIME is an asymmetric crypto-system of RSA-type, which uses composite moduli
of the form N = pd q. In particular, for HIME it is proposed d = 2 or d = 3.
The security proof of HIME is based on the assumption, that it is intractable tofactor such a modulus (that is, the probability to factor such a modulus efficiently is
negligible). We comment on the according part of the self-evaluation report (section
2.6) given by Hitachi Ltd.
The goal is to estimate the size for a HIME-modulus N such that we expect thesame computational work to factoring N as to factoring an RSA-modulus N 0 of
certain bit size. Specifically, the following claim is made:Claim 1: Let N = pd q denote a HIME-modulus, where p and q are of about equal
size, e.g. let |size(p) − size(q)| ≤ 1. Let N 0 = p0 q 0 denote a RSA-modulus, where p
and q are of about equal size, e.g. let |size(p0 ) − size(q 0 )| ≤ 1. Then
• if d = 2 then the expected computational work to factor the HIME-modulus
N of size 1344, 2304, and 4032 is about as much as the expected computational work to factor the RSA-modulus N 0 of size 1024, 2048, and 4096 bits,
respectively;

1 Selecting the Size of the Modulus pd q2

• if d = 3 then the expected computational work to factor the HIME-modulus
N of size 1536, 3072, and 4928 is about as much as the expected computational work to factor the RSA-modulus N 0 of size 1024, 2048, and 4096 bits,
respectively.
In order to justify the claim, two types of factoring algorithms have been taken
into account: General factoring algorithms with an expected running time only dependent of the modulus N itself, and special factoring algorithms with a running
time dependent of the largest prime factor P of the modulus N . The asymptotically fastest algorithms from these families are the Generalized Number Field Sieve(GNFS) and the Elliptic Curve Method (ECM). It has been pointed out that the
special algorithm from [BDG99] is not efficient for d = 2 or d = 3. We define
Lx [, c] = exp((ln x) (ln ln x)1− )(1)for all real x > e ≈ 2.71828 . . . and all real constants , c with 0 ≤  ≤ 1 and c > 0.
(In the self-evaluation report L is defined by Lx [, c] = exp((c+o(1))((ln x) (ln ln x)1− )),but it is more convenient to move the term o(1) out of the definition of L.) The
GNFS has an expected asymptotic running time of order of magnitude
1 q
LN [ , 3 64/9 + o(1)] ,
3

(2)

q

where 3 64/9 ≈ 1.923. By a theoretical modification of the GNFS due to Coppersmith it gets the slightly better expected asymptotic running time of order ofmagnitude√
1 q
3
LN [ , (92 + 26 13)/27 + o(1)] ,
(3)
3
q
√
where 3 (92 + 26 13)/27 ≈ 1.902. In the self-evaluation report the asymptotics 3 isassumed for the GNFS. We note that the authors of [RSA155] and [LV01] assumed
the asymptotics 2 for the GNFS, thus we recommend to use the asymptotics 2 here,
too.
The ECM has an expected asymptotic running time of order of magnitude
1 √LP [ , 2 + o(1)] .
2(4)

We note that the asymptotics 2 (or 3) and 4 haven’t rigorously proven, yet. However,
the assumptions of these asymptotics are accepted in general.
We also note that the ECM can be sped up for numbers of the form N = p2 q, see[PO96], this speed-up hasn’t been taken into account in the self-evaluation report(See the recent experimental result [ET02]). If the exponent d is large, then twoalgorithms are known for factoring the special form N = pd q in polynomial time
[BDG99] [CUS02].

1 Selecting the Size of the Modulus pd q

3

For all practical considerations and extrapolations the term o(1) has been omitted(as is customary), although if an extrapolation far out is made, one cannot neglectthat o(1) → 0, thus extrapolated running times will be an overestimate.
The current factoring records are: RSA-155, a 512-bit composite, has been split by
the GNFS in 2000, where approximately 8000 MIPS-years have been spent [RSA155];
a 55-digit factor, that is, a 183-bit factor, has been found by the ECM in 2001
(see http://www.loria.fr/~zimmerma/records/ecmnet.html). Thus, if N = pd q,
then N has to be much larger than 2512 , and p and q have to be much larger than
2183 .
It must be noted that ECM can be run in parallel without much communication
overhead, thus an ECM factorization could be (and have already been) distributed
over a network. On the other side, the GNFS works in two stages; the first stage(the sieving-stage) can also be run in parallel without much communication overhead
and thus is likewise suitable for distributed computation, while the second stage (thelinear-algebra-stage) has to be performed on a single node and requires exceptionalamounts of main memory. Therefore, a compound effort to find a factor by the
ECM using more unused resources that are available to the Internet is likely to findlarger factors (say 60 to 65 digits), merely using current computer technology.
We take the asymptotics 2 or even 3 for the GNFS and 4 for the ECM for granted.
The working hypothesis of the self-evaluation report is as follows:
Q

Hypothesis 1 Let d be a small integer and N = 0≤i≤d pi be a composite, where
the d + 1 prime factors pi are of about the same size, e.g. let |size(pi ) − size(pj )| ≤ 1
for all 0 ≤ i, j ≤ d. Then there exists an integer N0 such that for all composites
N as above, N ≥ N0 , the expected running time of the ECM exceeds the expectedrunning time of the GNFS.
The hypothesis is justified by the asymptotics for the GNFS and the ECM with N
given as in the hypothesis. For instance, the GNFS factors a 1024-bit RSA-modulus
faster than the ECM.
To estimate the size of N , N = p2 q or N = p3 q, such that factoring N by the ECM
is about as difficult as factoring an RSA-modulus N 0 of given size, the authors of
the self-evaluation report compared the asymptotics 3 and 4 for both algorithms
based on the special form of N as in the hypothesis. For convenience, the following
functions have been defined:
1 √  √
tEC = ln LP [ , 2] = 2 ln P ln ln P
2

and

q

1
tN F S = ln LN [ , 1.901] = 1.901 3 ln N (ln ln N )2
3
The estimation of the size of the HIME-moduli is demonstrated by two examples:1.1

Conclusion

4

1. Let N 0 be a 1024-bit RSA-modulus. How large must a HIME-modulus N = p2 q
be, such that the expected computational work to factor both with the best
known algorithms is about equal?
To do this, equations 3 and 4 have been equated, finally neglecting any Oconstants. For example, the authors define α = tN F S (1024 − bitN ) = CN F S +59.42, while tN F S (1024 − bitN ) ≈ 59.48, thus CN F S ≈ 0. There’s no comment
indicating why the constant is or can be neglected.
By means of trial or Newton-approximation (this hasn’t been made clear),
one gets thattN F S (1024 − bitN ) − tEC (448 − bitP ) = C − 0.28 for a constant
C that is implicitly neglected, and the authors concluded that the expectedcomputational work to factor N 0 with bit size 1024 by the GNFS is about asmuch as the expected computational work to factor N with bit size 3 · 488 =
1344 (with a factor of e0.28 ≈ 1.32, all other factors have been dropped).
2. A similar calculation for a HIME-modulus N = p3 q leads to size(N ) = 1536
when size(N 0 ) = 1024 for RSA-moduli N 0 .
This shall justify the initial claim, the other presented estimates.
Additionally we notice that Silverman estimated the key length of the Multi-Prime
RSA, PKCS #1 [PKCS], which uses the modulus n = p1 p2 ...pk where p1 , p2 , ...pk areprime numbers with the same size [Sil00]. He concluded that breaking a 1024-bit
RSA modulus is as hard as the 1024-bit modulus of the Multi-Prime RSA with 3
primes.

1.1

Conclusion

The estimation of the key sizes has been done with some bias and sloppiness. Our
objections were:
1. For the GNFS the asymptotics 3 has been used, while in recent research papers(e.g. [LV01] or [RSA155]) one finds the asymptotics 2. Thus, the authors
assumed an algorithm for factoring RSA-moduli that is too fast.
2. The speed-up of the ECM for special numbers of the form N = p2 q as describedin [PO96] [ET02] should be taken into account for the estimate.
3. The authors naively equated 3 and 4 without taking into account any data
points (such as 8000 MIPS-years spent for RSA-155).
4. Many assumptions made aren’t stated explicitly, these should be clarified.
Likewise, the overall model is not clearly explained.

1.1

Conclusion

5

Although the estimates are not grossly wrong, we would appreciate if the authors
would make their estimates with more care and precision. That is, the authors
should describe their model more precisely; they should not make implicit assumptions, and if the make them explicit, the authors should justify them clearly. The
authors should collect data points for ECM in order to equate the expected computational work for GNFS and ECM.

2 Proof of Security

2

6

Proof of Security

HIME is an asymmetric crypto-system of RSA-type, which uses composite moduli of
the form N = pd q. In particular, for HIME it is proposed d = 2 or d = 3. It is provedthat if HIME can be broken efficiently, then N can be factored efficiently with nonnegligible probability. Assuming the intractability of the factoring problem, HIME
cannot be broken efficiently with non-negligible probability.
We comment on the according part of the self-evaluation report given by Hitachi
Ltd. We mainly evaluate the correctness of the proof of Theorem 2.2 in the selfevaluation report.
We shortly review the encryption function of HIME(R). Let n be a k-bit public
modulus of HIME(R) and let G, H be two hash functions, where G : {0, 1}k0 →{0, 1}k−k0 −1 , H : {0, 1}k−k0 −1 → {0, 1}k0 for integers k0 , k1 such that 2k0 < k, n =k − k0 − k1 − 1 > 0. In the proof of HIME(R), the hash fucntion is considered as
the random oracle. The padding scheme of the HIME(R) for a n-bit message m iscomputed as follow:
x = s||(r ⊕ H(r)),

s = m0k1 ⊕ G(r).

(5)

Then y = x2 mod n is the ciphertext of the message m. This padding scheme ofHIME(R) is based on the OAEP conversion [BR94].
The techniques used in the security proof are similar with that of SAEP/SAEP+[Bon01]. In the security proof of HIME(R), the simulator tries to find the non-trivial
square root using the Coppersmith algorithm. The authors of HIME(R) proved thatthe success probability of the simulator becomes non-negligible in the random oracle
model using the adversary that breaks the semantically security against the adaptive
chosen ciphertext attack. A similar proof idea was discussed for the OAEP-RSA
with low encryption exponent e = 3 in the manuscript [Sho01b].
Because the security proof of HIME(R) follows from these well-studied standard
techniques, we have not noticed technical flaws in their proof. However, we havefound several editorial mistakes in the proof of Theorem 2.2. We list up thesemistakes in the following.

p. 10–11 (simulation of the find- and guess-stages)
There is a common omission in (3.1), (3.2), (4.1), and (4.2): Whenever h or g canbe found on the respective list (i.e. a previous oracle call is repeated), the previously
defined value Hh or Gg must be returned.

2.1

Conclusion

7

p. 11 (simulation of the decryption oracle)
The presentation is confusing: While steps (5.1) and (5.2) are performed for each(si , Hi ) and each (rj , Gj ), step (5.3) is not.
Also note that for consistency with the specification of the actual decryption procedure, the decryption oracle should return “reject” rather than ∗ in the second
branch of (5.3).

p. 14 (additional events of Game 1)
Note that event AskH (and thus, as a special case, also AskS) is impossible in Game 1.
According to (3.1) and (4.1) in the definition of the simulator (pp. 10–11), no h suchthat (h || x)2 ≡ y (mod N ) for some x ∈ {0, 1}k0 will ever be put on the H-list;
instead the simulation will be aborted when such a h is encountered. (Also cf. p. 11:“M does not return [to A] the answer of h which defines w∗ ”.)
HITACHI must change the definition of H-list. The goal of the simulation in the
proof is to find h as the query to random oracle H, which satisfies (h||x)e = y mod n
for some integer x and a given y. If H-list does not include such h, event AskH isempty. Thus they have to add the h in the first component of H-list before simulator
M terminates.

p. 15 (inequality (9))
There appears to be a typo in inequality (9): “Pr2 [W]” is probably intended to read
“Pr3 [W]”.
It is better to explain the meaning of the value  − 2qkG0 , which is a positive nonnegligible function because  is non-negligible and 2qkG0 is negligible.

2.1

Conclusion

We evaluated the security of HIME(R) based on the self-evaluation report, namely
the correctness of the proof of Theorem 2.2. There are several editorial mistakes in
the proof of Theorem 2.2, but the general outline of their proof is correct.

3 Comparison of HIME with other Crypto-Systems

38Comparison of HIME with other Crypto-Systems

In this section the security and the plaintext size of HIME(R) are compared withother cryptosystems. We compare HIME(R) with the RSA-OAEP [BR94], RSAOAEP+ [Sho01a], Rabin-SAEP [Bon01], and Rabin-SAEP+ [Bon01].

3.1

Comparison of Security Reduction

Let A denote an attacker that breaks one of the following crypto-systems (i.e. INDCCA2) in time t with probability ε. Then there exists an algorithm A0 that factors
the modulus N (pq for RSA and Rabin, pq d , d = 2, 3 for HIME) in time t0 withprobability ε0 . TC denotes the running time of Coppersmith’s algorithm, Ts and T̃
are as in the HIME report.

Running time t0 of A0

HIME

t + qH TC (N, 2) + qG qH Ts (k) + T̃ (k) + O(k)RSA-OAEP

2t + qH (qH + 2qG )O(k3 )RSA-OAEP+

O(t + qG qH Tf + (qG + qH 0 + qH + qD )k)Rabin-SAEP

t + O(qH + qG + qD )Rabin-SAEP+

t + O(qD qH TC (n, 2) + qD TC (n, 4))Success-Probability ε0 of A0

13

ε − qkG0

ε2
−ε
4



2

1 − qkG0

2

1 − qkD1 − qkD0
2

2

2qD qG +qD +qG
32+ 2qkD+ k−2k
0
2k0
2 1
2

ε−

qH 0 +qD
2k 1−(qD +1)qG
2k 0

ε 1 − 2qsD0 − 2qsD1
1
ε
6





D
D
1 − 2q
− 2q
2s 0
2s1



We assume that the numbers of queries qH , qG , and qD are same. The running
time of the security reduction of the Rabin-SAEP is the linear order of q, where q
is one of the qH , qG , and qD . The running times of the security reduction of othercryptosystems have the quadratic order of q. Therefore, the running time of the
security reduction of HIME is as fast as those of RSA-OAEP, Rabin-SAEP, andRabin-SAEP+.
The security parameters k0 , k1 of HIME and s0 , s1 are chosen enough large. Thenthe probabilities of security reduction of HIME, RSA-OAEP+, Rabin-SAEP, RabinSAEP+ are the order of O(ε), and that of RSA-OAEP is the order of O(ε2 ).
Therefore we conclude the security reduction of HIME is similar as that of the
Rabin-SAEP+.

3.2

Comparison of Plaintext Lengths

3.2

Comparison of Plaintext Lengths

9

They summarize the size of the plaintext and ciphertext in Table 5. The main
advantage of the HIME cryptosystem is the size of the plaintext. The size of theplaintext of 1344-bit HIME is 1088 bits, which is equal to or the largest among other
RSA/Rabin-type cryptosystems.

4 Comparison of Efficiency as Primitives

4

10

Comparison of Efficiency as Primitives

In this section we discuss the estimation of the efficiency in the self-evaluation reportof HIME. We discuss the estimation about the HIME cryptosystem, the RSA cryptosystem, the Rabin cryptosystem, the RSA-type cryptosystem modulo pk q [Tak98](We call it PkQ cryptosystem). In this document, we estimate the efficiency of thedecryption of the 1024-bit RSA/Rabin cryptosystem and the 1344-bit HIME/PkQ
cryptosystem.
Let P rimitive(sk, C) be the cryptographic primitives of these cryptosystems, where
sk is a secret key and C is a ciphertext. Let Check(M ) be the checking mechanism
using the random hash functions of these cryptosystems in order to achieve the
IND-CCA security. The whole decryption algorithm of these cryptosystems firstcomputes M = P rimitive(sk, C) for a given ciphertext C using the secret key
sk, and then check the correctness of the ciphertext by Check(M ). Because thecomputation of Check(M ) is very fast, we will estimate the primitive part of thedecryption algorithms in the following.
In the specification form (page 7), they state “The actual decryption speed mountaing size will be smaller than previous one because ours does not require Euclidean
algorithm for CRT”. However, this is misleading, although they insist that this is
one of the advantage of the HIME.
The standard RSA decryption using the CRT, which is described in the PKCS #1[PKCS], also does not require Euclidean algorithm, because the Garner’s algorithm
is used for the CRT. If we apply the Garner’s algorithm, the other RSA/Rabin-type
cryptosystems do not require an inversion operation for the CRT. We describe thedecryption algorithm of the RSA cryptosystem with CRT from PKCS #1 in thefollowing.
INPUT p,q, dp, dq, p_inv_q, C
OUTPUT M
1: Mp = mod_pow(C,dp,p);2: Mq = mod_pow(C,dq,q);
3: V = (Mq - Mp)*(p_inv_q) mod q; <--- pre-comp. 1/p mod q
5: Return M = Mp + p*V;
Algorithm 1: PKCS #1 Decryption
Here p and q are primes with same bit-length and the RSA modulus is pq. dp =d mod p − 1, dq = d mod q − 1, and p inv q = p−1 mod q are the secret key of the
PKCS #1. C is a ciphertext of the message M . mod pow(a, b, c) means ab mod c.
Note that there is no inversion during whole decryption process of the decryption of
PKCS #1. The overhead of the decryption algorithm over the computation of the4.1

Performance of the Rabin based Decryption

11

modular multiplications Mp = C dp mod p and Mq = C dq mod q is just 1 modular
multiplication of k bits and 1 multiplication of k bits and k bits, where k is the
bit-length of prime p (or q). They are at most 0.5 modular multiplication of 2k bits.
Therefore, if we estimate the efficiency based on section 3.2 of the self-evaluation
report of the HIME(R), the decryption time of the PKCS #1 for 1024-bit modulus
becomes 385 modular multiplications of 1024 bits. The estimations in Table 3 insection 3.2 of the self-evaluation report must be corrected.
On the contrary, HIME(R) always has at least one inversion during the decryption
process for p2 q. An inversion operation c−1 mod p is estimated about 30 times
slower in software than the modular multiplication c1 c2 mod p, where c, c1 , c2 areas large as p [OS01]. The coprocessor of the inversion is not equipped on manysmartcards. Therefore, the inversion is critical operation on them and the estimationmust carefully consider it. They do not state how the computation time of inversion
is estimated in the self-evaluation report of the HIME(R).
Takagi proposed an RSA-type cryptosystem using the modulus pd q [Tak98] [Tak01].
We call it the PkQ cryptosystem in the following. The decryption of the HIME
cryptosystem uses a similar technique with the PkQ cryptosystem. In section 3.2 ofthe self-evaluation report of HIME, they estimate the decryption time of the HIME
+ 11
in comparison with that of the PkQ as |p|+ 25. Moreover, they also
as |p|
3
3
3
6
stated “It has less modular multiplications than previous one” in section 2 of thespecification of HIME. However, these statements are misleading. We discuss theestimations are not correct in the following subsections. We conclude the decryptionof the PkQ cryptosystem is faster than that of the HIME. Our estimation of theoverheads is 17.7 modular multiplications for the HIME decryption and 14.8 modular
multiplications for the PkQ decryption for the 1344-bit modulus. Thus the total
decryption times are 275 for the HIME decryption and 272 for the PkQ decryption,
respectively.
For the comparison of the HIME decryption and the PkQ decryption we use thestandard algorithms described in book [MvOV97]. A multiplication of n bits andt bits requires (n + 1)(t + 1) single-precision multiplications (Algorithm 14.12 andNote 14.15 of [MvOV97]). A division of n bits by t bits requires (n − t)(t + 3)
single-precision multiplications (Algorithm 14.20 and Note 14.25 of [MvOV97]). Let
ab mod c be a modular multiplication of n bits, where a, b, and c are n-bit integers.
The modular multiplication of n bits is 2n2 + 5n + 1 single-precision multiplications(Algorithm 14.28 of [MvOV97]). We assume the computation time of an addition
and a subtraction is negligible, comparing with the multiplication or the division.

4.1

Performance of the Rabin based Decryption

We describe the decryption algorithm of the Rabin based decryption modulo p2 q in
the following. We use the secret key p inv q in addition to p and q as the PKCS #
does.

4.2

Performance of the HIME Decryption

12

INPUT p, q, p_inv_q, C
OUTPUT M
0: Check C mod p and C mod q are quadratic residue;
1: Mp = mod_pow(C,(p+1)/4,p);2: Mq = mod_pow(C,(q+1)/4,q);
3: V = (+-Mq - (+-Mp))*(p_inv_q) mod q; <--- pre-comp. 1/p mod q
4: M = +-Mp + p*V;
5: Find the proper M from 4 ambiguities
6: Return M;
Algorithm 2: Rabin based decryption
Assume that the value p−1 mod q is pre-computed. Let k be the bit-length ofprime p (or q). We estimate the computation efficiency of step 3 and step 4, which
are the overhead parts from the two modular exponentiations C (p+1)/4 mod p andC (q+1)/4 mod q. There are 4 different solutions and we estimate the efficiency in thecase of finding all the four solutions.
We conclude that the overhead of the Rabin based decryption is at most 1.5 modular
multiplications of 2k bits. Therefore, if we estimate the efficiency based on section
3.2 of the self-evaluation report, the decryption time of the Rabin based decryption
becomes 386 modular multiplications of 1024 bits with pre-computation of p−1 modq. The details of the estimation is as follows:
Theorem 1 Fro step 3 and step 4 of the HIME decryption (algorithm 3), we need
(1)2 modular multiplications of k bits, (2)4 multiplications of k bits and k bits,
where k is the bit-length of the prime p of q. If the parameter p−1 mod q is not
pre-computed, we need (1)2 modular multiplications of k bits, (2)4 multiplicationsof k bits and k bits, and (3)1 modular inverse of k bits.
Proof: In step 3 we compute four values V = (±Mq − (±Mp )) ∗ (p inv q) mod q
and we assign them as V0,0 = (Mq − Mp ) ∗ (p inv q) mod q, V1,0 = (Mq + Mp ) ∗(p inv q) mod q, V0,1 = −V1,0 mod q, and V1,1 = −V0,0 mod q. We need 2 modular
multiplications of k bits. If p−1 mod q is not pre-computed, we need one more
modular inverse of k bits.
In step 4 we compute four values M = ±M p + p ∗ V and we assign them as M0,0 =Mp + p ∗ V0,0 , M1,0 = −Mp + p ∗ V1,0 , M0,1 = Mp + p ∗ V0,1 , and M1,1 = −Mp + p ∗ V0,0 .
We need 4 multiplications of k bits.

4.2

Performance of the HIME Decryption

We describe the decryption algorithm of the HIME modulo for the modulus p2 q in
the following. In section 2.2.1 of the specification of the HIME(R), the secret key

4.2

Performance of the HIME Decryption

13

is only the primes p and q. In section 3.3, the secret keys are not only p and q but
also (p + 1)/4, (q + 1)/4, and p−1 mod q. We do not understand which secret keys
are the proper specification of the HIME(R). If the parameters p−1 mod q and pq
are pre-computed, the decryption speed of the HIME(R) can be improved.
INPUT p, q, p_inv_q, pq, C
OUTPUT M
0: Check C mod p and C mod q are quadratic residue;
1: Mp = mod_pow(C,(p+1)/4,p);2: Mq = mod_pow(C,(q+1)/4,q);3:
r0 = +-Mp mod p;4:
r1 = (+-Mq - r0)*(p_inv_q) mod q; <--- pre-comp. 1/p mod q
5:
R1 = r0 + p*r1 ;6:
E = C - R1^2 mod p^2q;
7:
F = E/pq;8:r2 = F*(2r0)^{-1} mod p;<--- inversion modulo p.
9: M = R1 + (pq)*r2;
10: Find the proper M from 4 ambiguities
11: Return M;
Algorithm 3: HIME decryption
Assume that the values p−1 mod q and pq are pre-computed as secret keys. Let kbe the bit-length of prime p (or q). We estimate the computation efficiency fromstep 3 to step 9 of the HIME decryption, which is the overhead part from the twomodular exponentiations C (p+1)/4 mod p and C (q+1)/4 mod q. There are 4 different
solutions and we estimate the efficiency in the case of finding all the four solutions.
From step 3 to step 9 of the HIME decryption (algorithm 3), we need 64k 2 +100k+20
single-precision multiplications and 2 modular inverses of k bits, where k is the bitlength of the prime p (or q) (See theorem 2). We estimate in the case of k = 448,
which is the 1344-bit HIME cryptosystem. A modular multiplication of 1024 bits
is 2 ∗ (1024)2 + 5 ∗ (1024) + 1 = 2, 102, 273 single-precision multiplications. The
overhead of the HIME decryption without the two modular inverses is 64 ∗ (448)2 +100 ∗ 448 + 20 = 12, 889, 876 single-precision multiplications. A modular inverse ofk bits is 30 times as fast as a modular multiplication [OS01]. Thus we estimate
the modular inverse of k bits requires 30 ∗ (2 ∗ (448)2 + 5 ∗ 448 + 1) = 12, 109, 470
single-precision multiplications. Thus total overhead is 37, 108, 816 single-precisionmultiplications. We conclude that the overhead of the HIME decryption is 17.7
modular multiplications of 1024 bits with the pre-computations of p−1 mod q and
pq. The details of the estimation is as follows:
Theorem 2 From step 3 to step 9 of the HIME decryption (algorithm 3), we need(1)64k 2 + 100k + 20 single-precision multiplications and (2)2 modular inverses of kbits, where k is the bit-length of the prime p of q. If the parameters p−1 mod q and4.2

Performance of the HIME Decryption

14

pq are not pre-computed, we need (1)65k 2 +102k +21 single-precision multiplicationsand (2)3 modular inverses of k bits.
Proof: We refer the decryption algorithm in section 3.7 of the specification of the
HIME.
In step 3 we compute two values r0 = ±Mp mod p, where we assign them as r0,0 =Mp mod p and r0,1 = −Mp mod p. This computation is negligible.
In step 4 we compute four values r1 = (±Mq − r0 ) ∗ (p−1 ) mod q and we assign
them as r1,00 = (Mq − r0,0 ) ∗ (p−1 ) mod q, r1,01 = (Mq − r0,1 ) ∗ (p−1 ) mod q, r1,10 =(−Mq −r0,0 )∗(p−1 ) mod q, and r1,11 = (−Mq −r0,1 )∗(p−1 ) mod q. We need 4 modular
multiplications of k bits, which is 8k 2 + 20k + 4 single-precision multiplications. If
p−1 mod q is not pre-computed, we need an additional modular inverse of k bits.
In step 5 we compute four values R1 = r0 + p ∗ r1 and we assign them as R0,0 =r0,0 + p ∗ r1,00 , R0,1 = r0,1 + p ∗ r1,01 , R1,0 = r0,0 + p ∗ r1,10 , and R1,1 = r0,1 + p ∗ r1,11 .
We need 4 multiplications of k bits and k bits, which is 4k 2 + 8k + 4 single-precisionmultiplications.
In step 6 we compute E = C − R12 mod p2 q and we assign them as E0,0 = C −
2
2
2
R0,0
mod p2 q, E0,1 = C − R0,1
mod p2 q, E1,0 = C − R1,0
mod p2 q, and E1,1 = C −2
2
R1,1 mod p q. The bit length of Ri,j for i, j = 0, 1 is 2k. We need 4 multiplicationsof 2k bits and 2k bits, and 4 division of 4k bits by 3k bits, which is 28k 2 + 28k + 4
single-precision multiplications.
In step 7 we compute F = E/(pq) and we assign them as F0,0 = E0,0 /(pq), F0,1 =E0,1 /(pq), F1,0 = E1,0 /(pq), and F1,1 = E0,1 /(pq). We need 4 divisions of 3k bits by
2k bits, which is 8k 2 + 12k single-precision multiplications.
In step 8, we compute r2 = F ∗ (2r0 )−1 mod p and we assign them as r2,00 =F0,0 ∗ (2r0,0 )−1 mod p, r2,01 = F0,1 ∗ (2r0,1 )−1 mod p, r2,10 = F1,0 ∗ (2r0,0 )−1 mod p,
and r2,11 = F1,1 ∗ (2r0,1 )−1 mod p. The value r0 is not same for each decryption
and we cannot pre-compute the value (2r0 )−1 mod p. Therefore, we need 2 modular
inversions of k bits, and 4 modular multiplications of k bits, which is 8k 2 + 20k + 4
single-precision multiplications.
Finally, in step 9, we compute M = R1 +(pq)∗r2 and we assign M00 = R0,0 +(pq)∗r2,00
M01 = R0,1 + (pq) ∗ r2,01 M10 = R1,0 + (pq) ∗ r2,10 , and M11 = R1,1 + (pq) ∗ r2,11 . We
need 4 multiplications of k bits and 2k bits, which is 8k 2 + 12k + 4 single-precisionmultiplications.

4.3

Performance of the PkQ Decryption

4.3

Performance of the PkQ Decryption

15

We describe the fast decryption algorithm of the Rabin version of the PkQ cryptosystem. The secret keys of the PkQ cryptosystem are p, q, (p2 )−1 mod q, and p2 .
The general description is as follows:
INPUT p, q, p2_inv_q, p^2, C
OUTPUT M
0: Check C mod p and C mod q are quadratic residue;
1: Mp = mod_pow(C,(p+1)/4,p);2: Mq = mod_pow(C,(q+1)/4,q);3:
F = (+-Mp)^2 mod p^2;
4:
E = C - F mod p^2;
5:
B = E/p;6:
K = (+-Mp)*B*(2*F)^{-1} mod p; <--- inversion modulo p
7:
A = +-Mp + p*K;
8: V = (+-Mq - A)*(p2_inv_q) mod q; <--- pre-comp. 1/p^2 mod q
9: M = +-Mp + (p^2)*V;
10: Find the proper M from 4 ambiguities
11: Return M;
Algorithm 4: PkQ decryption
Assume that the values p−1 mod q and p2 are pre-computed as secret keys. Let kbe the bit-length of prime p or q. We estimate the computation efficiency fromstep 3 to step 9, which is the overhead part from the two modular exponentiations
C (p+1)/4 mod p and C (q+1)/4 mod q. There are 4 different solutions and we estimate
the efficiency in the case of finding all the four solutions.
From step 3 to step 9 of the PkQ decryption (algorithm 4), we need 48k 2 + 88k + 16
single-precision multiplications and 2 modular inverse of k bits, where k is the bitlength of the prime p of q (See theorem 3). We estimate in the case of k = 448,
which is the 1344-bit PkQ cryptosystem. A modular multiplication of 1024 bits is2∗(1024)2 +5∗(1024)+1 = 2, 102, 273 single-precision multiplications. The overheadof the PkQ decryption without two modular multiplications is 34∗(448)2 +72∗448+
16 = 6, 856, 208 single-precision multiplications. A modular inverse of k bits is 30
times as fast as a modular multiplication [OS01]. Thus we estimate the modular
inverse of k bits requires 30 ∗ (2 ∗ (448)2 + 5 ∗ 448 + 1) = 12, 109, 470 single-precisionmultiplications. Thus total overhead is 33, 892, 172 single-precision multiplications.
We conclude that the overhead of the PkQ decryption is 14.8 modular multiplicationsof 1024 bits with the pre-computation of p−1 mod q and p2 . The details of theestimation is as follows:
Theorem 3 From step 3 to step 9 of the PkQ decryption (algorithm 4), we need
(1)34k 2 + 72k + 16 single-precision multiplications, and (2)2 modular inverses of k

4.4

Conclusion

16

bits, where k is the bit-length of the prime p of q. If the parameters (p2 )−1 mod q andp2 are not pre-computed, we need (1)35k 2 + 74k + 17 single-precision multiplications,and (3)3 modular inverses of k bits.
Proof: In step 3, we compute F = (±Mp )2 mod p2 and we assign them as F0 =(Mp )2 mod p2 and F1 = (p − Mp )2 mod p2 . Because Mp and p − Mp are smaller thanp, the two values (Mp )2 and (p−Mp )2 are smaller than p3 . We need 2 multiplicationsof k bits, which is 2k 2 + 4k + 2 single-precision multiplications.
In step 4, we compute E = C −F mod p2 and we assign them as E0 = C −F0 mod p2
and E1 = C − F1 mod p2 . We need 2 modular reduction of 3k bits by 2k bits, which
is 4k 2 + 6k single-precision multiplications.
In step 5, we compute B = E/p and we assign them as B0 = E0 /p and B1 =E1 /p. We need 2 divisions of 2k bits by k bits, which is 2k 2 + 6k single-precisionmultiplications.
In step 6, we compute K = (±Mp ) ∗ B ∗ (2 ∗ F )−1 mod p and we assign them as
K0 = (Mp ) ∗ B0 ∗ (2 ∗ F0 )−1 mod p and K1 = (−Mp ) ∗ B1 ∗ (2 ∗ F1 )−1 mod p. The
values F0 and F1 cannot be computed in advance. We need 2 modular inverses of kbits, and 4 modular multiplications of k bits, which is 8k 2 + 20k + 4 single-precisionmultiplications.
In step 7, we compute A = (±Mp ) + p ∗ K and we assign them as A0 = Mp + p ∗ K0
and A1 = Mp + p ∗ K1 . We need 2 multiplications of k bits and k bits, which is
2k 2 + 4k + 2 single-precision multiplications.
In step 8, we compute V = (±Mq − A) ∗ (p2 inv q) mod q and we assign them as
V0,0 = (Mq − A0 ) ∗ (p2 inv q) mod q, V1,0 = (Mq − A1 ) ∗ (p2 inv q) mod q, V0,1 =(−Mq − A0 ) ∗ (p2 inv q) mod q, and V1,1 = (−Mq − A1 ) ∗ (p2 inv q) mod q. We
need 4 modular multiplications of k bits, which is 8k 2 + 20k + 4 single-precisionmultiplications.
Finally in step 9, we compute M = A + (p2 ) ∗ V and we assign them as M0,0 =A0 +(p2 )∗V0,0 , M1,0 = A1 +(p2 )∗V1,0 , M0,1 = A0 +(p2 )∗V0,1 , and M1,1 = A1 +(p2 )∗V1,1 .
We need 4 multiplications of 2k bits and k bits, which is 8k 2 +12k+4 single-precisionmultiplications.

4.4

Conclusion

In Table 1, we summarize the comparison among the HIME decryption, the RSA
decryption, the Rabin based decryption, and the PkQ decryption [Tak98]. The
dominant computation time of the HIME or the PkQ decryption is the computationof both C (p+1)/4 mod p and C (q+1)/4 mod q, which is estimated 257.3 for 1344-bit

4.4

Conclusion

17

modulus. The numbers in the table are the number of the modular multiplicationof 1024 bits.

Table 1: Comparison of efficiency among several schemes
1024-bit RSA
385

1024-bit Rabin386

1344-bit HIME
275

1344-bit PkQ
272

We conclude that although the 1344-bit HIME decryption is faster than the 1024-bit
RSA/Rabin decryption, it is slower than the 1344-bit PkQ decryption.
Note that in theorem 2 and theorem 3 we proved the decryption algorithm of the
HIME cryptosystem is still slower than that of the PkQ cryptosystem even if theirpre-computations are not carried out.
The secret keys of the HIME are p, q without pre-computation or p, q, p−1 mod q, pq
with pre-computation. The secret keys of the PkQ are p, q without pre-computationor p, q, (p2 )−1 mod q, p2 with pre-computation. Therefore, the total secret key sizesof the HIME cryptosystem and the PkQ cryptosystem are same for the same bitlength modulus.

References

18

References[BR94] M. Bellare and P. Rogaway, “Optimal asymmetric encryption - How to
encrypt with RSA,” Advances in Cryptology - EUROCRPT’94, LNCS 950,
pp.92-111, 1994.
[Bon01] D. Boneh, “Simplified OAEP for the RSA and Rabin Functions,” Advancesin Cryptology – CRYPTO 2001, LNCS 2139, pp.275-291, 2001.
[BDG99] D. Boneh, G. Durfee, and N. Howgrave-Graham, “Factoring N = pr q forlarge r,” Advances in Cryptology – CRYPTO’99, LNCS 1666, pp.326-337,
1999.
[Bre00] R. Brent, “Recent progress and prospects for integer factorisation algorithms,” 6th Annual International Conference, COCOON 2000, LNCS 1858,pp.3-22, 2000.
[CUS02] K. CHIDA, S. UCHIYAMA, and T. SAITO, “A new factoring method of
integers N = pr × q for large r,” IEICE Trans. Fundamentals, Vol.E85-A No.5
pp.1050-1053, 2002.
[ET02] P. Ebinger and E. Teske, “Factoring N = pq 2 with the Elliptic Curve
Method,” Technical Report of CACR, University of Waterloo, CORR 2002-02,
2002.
[ECM98] ECMNET Project, http://www.loria.fr/~zimmerma/records/ecmnet.html[HIME01] HIME(R), Specification and Self-Evaluation Report, Hitachi Ltd.
http://www.sdl.hitachi.co.jp/crypto/hime/[MvOV97] A. J. Menezes, P. C. van Oorschot, and S. A. Vanstone. Handbook of
applied cryptography, CRC Press, 1997.
[LV01] A. Lenstra, E. Verheul, “Selecting cryptographic key sizes,” Journal of Cryptology, 14 (4), p.255-293, 2001.
[OS01] K.Okeya and K.Sakurai, ”Efficient elliptic curve cryptosystems from a scalarmultiplication algorithm with recovery of the y-coordinate on a Montgomeryform elliptic curve”, CHES2001, LNCS 2162, pp.126-141, Springer-Verlag,
2001.
[PO96] R. Peralta and E. Okamoto, “Faster factoring of integers of a special form,”
IEICE Trans. Fundamentals, Vol.E79-A, No.4, pp.489-493, 1996.
[PKCS] Public-Key Cryptography Standards, PKCS # 1, RSA Laboratories,
http://www.rsasecurity.com/rsalabs/pkcs/

References

19[RSA155] S. Cavallar, B. Dodson, A. K. Lenstra, W. Lioen, P. L. Montgomery,B. Murphy, H. te Riele, K. Aardal, J. Gilchrist, G. Guillerm, P. Leyland, J.
Marchand, F. Morian, A. Muffett, C. Putnam, C. Putnam, and P. Zimmermann, “Factorization of a 512-Bit RSA Modulus,” Advances in Cryptology –EUROCRYPT 2000, LNCS1807, pp.1-18, 2000.
[Sho01a] V. Shoup, “OAEP reconsidered,” Advances in Cryptology – CRYPTO
2001, LNCS 2139, pp.239-259, 2001.
[Sho01b] V. Shoup, “A proposal for an ISO standard for public key encryption,”
http://shoup.net/[Sil00] R. Silverman, “A cost-based security analysis of symmetric andasymmetric key lengths,” RSA Laboratories Bulletin, No.13, (2000).
http://www.rsasecurity.com/rsalabs/bulletins/bulletin13.html[Tak98] T. Takagi, “Fast RSA-Type Cryptosystem Modulo pk q,” Advances in Cryptology - CRYPTO ’98, LNCS 1462, pp.318-326, 1998.
[Tak01] T. Takagi, “New Public-Key Cryptosystem with Fast Decryption,” PhD
Thesis, Technische Universtät Darmstadt, Germany, 2001. (available fromhttp://elib.tu-darmstadt.de/diss/000104/)