Report on Present State of
OK-ECDSA and OK-ECDH Evaluation(screening evaluation)
January 28, 2002
Atsushi Shimbo, Member
Public-Key Cryptography
Subcommittee1OK-ECDSA(submitter’s claims)• Category: Signature• Security basis: Discrete logarithm problem on
Montgomery-form elliptic curve• Provable security: The scheme is the unmodified ECDSA scheme.
It has no established proof of security.
(The submitter cites Brown’s results using a generic group model.)• Characteristics:– Strong ability to withstand side channel attacks– Well-suited to IC card implementations; uses only a small amount of memory
when running.

• SW implementation information:
Signature generation: 11.0ms; signature verification: 21.6msec(Pentium III 866MHz)
2

OK-ECDH(submitter’s claims)• Category: Key agreement• Security basis: Discrete logarithm problem on
Montgomery-form elliptic curve• Provable security: The scheme is the unmodified ECDH scheme.
Although there are no security proofs,
the scheme is heuristically believed to be
secure against passive attacks.
• Characteristics:– Strong ability to withstand side channel attacks– Well-suited to IC card implementations; uses only a small
amount of memory when running.
• SW implementation information: Key agreement: 11.0ms(Pentium III 866MHz)
3

OK-ECDSA and OK-ECDH
Technical Characteristics• Use of randomized projective coordinates on Montgomery-form
elliptic curve– Same calculation sequence, regardless of secret information– Values to be calculated are randomized.

• Introduction of technique for reproducing Y coordinate inMontgomery-form elliptic curve addition (without using Ycoordinate)• The schemes are the unmodified ECDSA and ECDH schemes– The only differences are at the primitive implementation level.

• Montgomery-form elliptic curves are a restricted class of ellipticcurves, but approximately 40% of general elliptic curves can betransformed into the Montgomery-form.
4

Screening evaluation• OK-ECDSA and OK-ECDH have common technicalcharacteristics, so the same three evaluators wererequested to evaluate them.
• Cryptographic technique specifications:– No unclear or questionable points.
– Some feel the recommended values for the elliptic curveparameters are missing (partially).

• Self-evaluation– Comments are concentrated on the ability to withstand sidechannel attacks.
5Evaluation comments• Ability to withstand side channel attacks not sufficientlyevaluated– The claim that these schemes have a strong ability to withstandside channel attacks seems justified, but there is not quantitativeevaluation based on implementations.
– The evaluations of the submitter are only theoretical observations.
Because issues at the implementation level were not discussed,
there is a possibility that implementations could have poor ability
to withstand side channel attacks.
– Implementations of these schemes need to be compared to othertechniques. In addition, the schemes must be evaluated withconsideration for platform characteristics and computation cycles.
– The same applies to the amount of required memory.
– There are no smart card implementation evaluation results.
– The grounds for the hardware implementation results are notpresented.
6