Accelerating public-key cryptography by precomputing randomly generated pairs
US6091819A · kind A · utility
Assignee
Inventors
Key dates
| Filing date | Aug 15, 1997 |
| Grant date | Jul 18, 2000 |
| Priority date | — |
| Expiry date | Aug 15, 2017 |
Classification
- Technology area (CPC H)Electricity
- CPC primaryH04L2209/26
- WIPO fieldDigital communication
- WIPO sectorElectrical engineering
Abstract
Fast methods for generating randomly distributed pairs of keys for use in public-key cryptography use a precomputation step to reduce the online task of discrete exponentiation with long integers. After the precomputation is completed, the online steps required to produce a key pair are reduced to a small number .kappa. (about 16) of modular multiplications with long integers. The key pairs are of the form (k, g.sup.k) or (k, k.sup.e) where the exponentiations are computed modulo a long number p, g and e are fixed integers, and k is randomly distributed modulo ord(g), where ord(g) is the smallest positive integer that satisfies g.sup.ord(g) modulo p=1. The complexity of doing the precomputation step is itself about n exponentiation and may be accelerated to the same as two exponentiations, but the precomputation step needs to be done only very infrequently. Under easily achieved conditions, an adversary cannot analyze enough key pairs to gain a significant advantage from the knowledge that the method is being used.
Source: USPTO / EPO open patent data. Objective bibliographic and citation counts.