Cryptography – Particular algorithmic function encoding
Patent
1994-07-08
1995-12-26
Gregory, Bernarr E.
Cryptography
Particular algorithmic function encoding
380 9, 380 10, 380 16, 380 23, 380 30, 380 49, 34082531, 34082534, 235380, H04L 928, H04L 900, H04N 7167
Patent
active
054795117
DESCRIPTION:
BRIEF SUMMARY
The present invention relates to a method, to a sender apparatus and to a receiver apparatus for modulo operation.
BACKGROUND
In access control systems, e.g. pay TV systems, square, or more general, d-th roots modulo X are used where X is a composite number having at least two large prime factors. Typically the length of such a number X (denoted .vertline.X.vertline.) is 64 bytes.
If a sender, e.g. a smart-card, communicates with a receiver only few data are transmitted in order to save time. But this results in an increased number of computation operations in the sender and/or receiver.
INVENTION
It is one object of the invention to disclose a method for time-reduced modulo operations. This object is reached by the inventive method disclosed in claim 1.
In principle the inventive method consists in secure sending of a number S=D mod X or of a set of numbers S(j)=D(j) mod X, j=1, . . . ,i, from a sender device 28 to a receiver device 27, whereby X is a product of at least two big prime numbers and D is greater than X, comprising the following steps: device; E(j)=D(j)+A(j)*X, whereby X is stored in said sender, or calculating in said sender a set of values E(j)= D(j)*B, whereby a fixed number B=A*X is stored in said sender; from said sender to said receiver; number X is stored in said receiver device.
Advantageous additional embodiments of the inventive method are resulting from the respective dependent claims.
It is a further object of the invention to disclose a sender apparatus which utilizes the inventive method. This object is reached by the inventive apparatus disclosed in claim 6.
In principle the inventive sender apparatus consists in first computation means 25, first memory means 26 which are connected to said first computation means and first data exchange means 24 which are connected to said first computation means, whereby either means select said random number A or random numbers A(j) and calculate said value E=D+A*X or calculate said set of values E(j)=D(j)+A(j)*X or computation means calculate said set of values E(j)=D(j)+B of values E(j) to said receiver device 27.
Advantageous additional embodiments of the inventive sender apparatus are resulting from the respective dependent claims.
It is a further object of the invention to disclose a receiver apparatus which utilizes the inventive method. This object is reached by the inventive apparatus disclosed in claim 7.
In principle the inventive receiver apparatus consists in second computation means 22, second memory means 21 which are connected to said second computation means and second data exchange means 23 which are connected to said second computation means, whereby said second memory means store said modulus X and said second computation means calculate the modulo function S=E mod X of said value E or calculate a set of modulo functions S(j)=E(j) mod X of said set of values E(j).
Advantageous additional embodiments of the inventive receiver apparatus are resulting from the respective dependent claims.
The invention is applicable when a first cryptographic device (sender) communicates with a second cryptographic device (receiver), especially when the devices use a modulo-based protocol. Thereby the required number of modular operations is reduced or even eliminated. It can be avoided to do modular operations by the first device.
This is particularly advantageous when said first device, e.g. a smart-card, has a weaker computional power (e.g. less RAM and/or ROM capacity, slower clock rate) than said second device (e.g. a powerful processor acting as a verifier).
There are such access control systems where all the numbers appearing in the first ("weaker") device have a size n*.vertline.X.vertline. bytes before modular reduction, where n is a very small integer, typically 2 or 3.
There are different variants of the inventive method.
Let D be a number of length n,*.vertline.X.vertline. bytes.
The sender wishes to communicate S=D mod X to the receiver. For avoiding the modular reduction the sender chooses a random number A, computes E=D+A,
REFERENCES:
patent: 4306111 (1981-12-01), Lu et al.
patent: 5231668 (1993-07-01), Kravitz
J. H. Green, Jr. et al, "An Error-Correcting Encoder and Decoder of High Efficiency"; Proc.s of the I.R.E., (vol. 46, No. 10; Oct., 1958; pp. 1741-1744).
Philips Telecommunication Review, vol. 47, No. 3, Sep. 1989, Hilversum NL, pp. 1-19, "The Smart Card: A High Security Tool in EDP", By R. C. Perreira.
Proceedings of Crypto 90, 11-15 Aug. 1990, Berlin (DE), D. de Waleffe and J.-J. Quisquater, "Corsair: A Smart Card for Public Key Cryptosystems" pp. 502-513.
Recherche Operationnelle, vol. 24, No. 3, 1990, D. Naccache de Paz and H. Msilti, "A New Modulo Computation Algorithm", pp. 307-313.
Emanuel Peter M.
Gregory Bernarr E.
Shedd Robert D.
Thomson Consumer Electronics S.A.
Tripoli Joseph S.
LandOfFree
Method, sender apparatus and receiver apparatus for modulo opera does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method, sender apparatus and receiver apparatus for modulo opera, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method, sender apparatus and receiver apparatus for modulo opera will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-1375094