 |
|
|
|
|
|
 Title: |
EP0449349B1:
Method for the modular reduction of numbers[German][French]
[ Derwent Title ]
|
Country:
Kind: |
EP European Patent Office (EPO)
B1 PATENT SPECIFICATION i
(See also:
EP0449349A1 )
|
| |
| Inventor: |
see Assignee
|
| Assignee: |
Koninklijke PTT Nederland N.V.
News, Profiles, Stocks and More about this company
|
| Published / Filed: |
1994-04-27
/ 1991-03-12
|
| Application Number: |
EP1991000200523
|
| IPC Code: |
Advanced:
G06F 7/72;
G09C 1/00;
G09C 5/00;
H04L 9/30;
Core:
G06F 7/60;
H04L 9/28;
more...
IPC-7:
G09C 1/00;
G09C 5/00;
H04L 9/30;
|
| ECLA Code: |
H04L9/30L; G06F7/72;
|
| Priority Number: |
|
| Abstract: |
[From equivalent
EP0449349A1]
In cryptographic techniques which are based on the discrete logarithm problem, use is made of exponentiation modulo large number. If, in this method, the exponentiation is first carried out completely and the modular reduction is only carried out thereafter, this requires very considerable computation time and a very large memory capacity. It is known that the exponentiation can be accelerated by iteratively multiplying and squaring, with a modular reduction after each step. The invention provides a method of also accelerating the modular reduction at the same time, as a result of which the exponentiation modulo large number can be further accelerated. For this purpose, the invention describes a protocol for a modular reduction of a 2n-digit number x in a number system with base b to obtain an n-digit remainder, in which use is made of a specific modulus p which satisfies p = bn - a, where 0 < a < b. The method according to the invention does not reduce the security of the cryptographic system for which the modular exponentiation is carried out.
|
| INPADOC Legal Status: |
Show legal status actions
Family Legal Status Report
|
| Designated Country: |
AT BE CH DE DK ES FR GB GR IT LI LU NL SE
|
| Family: |
Show 12 known family members
|
First Claim:
Show all claims |
1. Method for the modular reduction of a not more than 2n-digit number x to obtain a not more than n-digit remainder r in accordance with the formula r ≡ x (mod p), where p is the chosen modulus, for the purpose of cryptographic calculations which are based on the general discrete logarithm problem in a number system with base b, in which method p is a n-digit number for which it holds true that p = bn - a, where 0 < a < b.
[German]
[French]
|
Description
Expand description |
[From equivalent
EP0449349A1]
The invention relates to a method for the modular reduction of a not more than 2n-digit number x to obtain a not more than n-digit remainder in accordance with the formula
r ≡ x (mod p) , where p is the chosen modulus, for the purpose of cryptographic calculations which are based on the general discrete logarithm problem in a number system with base b.
|
