# US 5,351,298 A · Cryptographic communication method and apparatus

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 5,351,298 A
- Document ID: US5351298A
- Status: Granted
- Kind: A
- Application number: 07/953,832
- Filed: 1992-09-30
- Granted: 1994-09-27
- Earliest claimed: 1991-09-30
- Inventors: Peter J. Smith
- Web page: https://patentgrep.com/patent/US5351298A

## CPC

- H04L 9/302: {involving the integer factorization problem, e.g. RSA or quadratic sieve [QS] schemes}
- H04L 9/3247: {involving digital signatures}
- H04L: TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION (arrangements common to telegraphic and telephonic communication H04M)

## Abstract

A public key cryptographic system uses Lucas functions as the basis for encoding and decoding messages. An encoding device and a decoding device are linked by a communication channel. The first device is able to be actuated by some message to be transmitted, M, as well as an encryption key, E, so as to form a cryptogram, C, so that C can be sent over the communication channel to a decoding device. The encryption key, E, is a pair of positive whole numbers, e and N, which match the decryption key, D, of the second decoding device. The message M must usually be broken down into blocks, M.sub.i, such that each is greater than or equal to zero and less than or equal to N-1. N is a composite number--i.e. it is made up of at least two prime numbers, p and q, such that N=p.multidot.q. The cryptographic transformation done by the encoding device can be described using the notation of Lucas functions. It is, for each ith block of message M which produces a matching ith block of the cryptogram C: C.sub.i =V.sub.e (M.sub.i,1)(modulo N) where e has been chosen to be relatively prime to all of (p-1), (q-1), (p+1) and (q+1).

## Claims

### Claim 1

A cryptographic communications system for communicating securely over an insecure communications channel by transmitting an electronic signal message from a transmitter to a receiver comprising means for enciphering the message with an encryption key at the transmitter to form a cryptogram, means for transmitting the enciphered message from the transmitter to the receiver, means for deciphering the enciphered message at the receiver with a decryption key, wherein the means for enciphering the message as a cryptograph at the transmitter comprises computation means which encodes the message by means of a higher order linear recurrence chosen from the class of Lucas functions.

### Claim 2 (depends on 1)

A cryptographic communications system as recited in claim 1, wherein:
the encryption key includes a pair of encryption numbers e and N;
the decryption key includes a set of decryption numbers D;
and the decryption numbers of the set D are derived from e and at least two prime factors p and q of N.

### Claim 3 (depends on 2)

A cryptographic communications system as recited in claim 2, further including means to digitize a message, and means to separate said digitized message M into sections M.sub.i, each said section comprising a number greater than or equal to zero, and less than N.

### Claim 4 (depends on 3)

A cryptographic communications system as recited in claim 3, wherein each section M.sub.i of the message M is encoded to produce a matching section C.sub.i of said cryptogram, according to the following means:
C.sub.i =V.sub.e (M.sub.i,1) (modulo N)
wherein V.sub.e is the e.sup.th Lucas function with respect to (M.sub.i,1) (modulo N).

### Claim 5 (depends on 4)

A cryptographic communications system as recited in claim 4, wherein e is relatively prime to all of
(p-1), (q-1), (p+1) and (q+1).

### Claim 6 (depends on 4)

A cryptographic communications system as recited in claim 4, wherein the set of numbers D is made up of at least four positive whole numbers, d.sub.j, where j comprises one of 1, 2, 3 or 4;
one of these numbers being calculated from each particular cryptogram block, C.sub.i, in the following manner:
a value .DELTA..sub.i is calculated as C.sub.i.sup.2 -4;
.DELTA. is determined to be either a quadratic residue or a quadratic non-residue of each of the prime factors of N;
the value of d.sub.j is determined in relation to .DELTA. as the multiplicative inverse of e, modulo the least common multiple of each prime factor of which .DELTA..sub.i can be a quadratic residue -1 and each prime factor of which .DELTA..sub.i can be a quadratic non-residue +1
resulting in one of at least four values;
and wherein the decryption of said cryptogram C into a message M' is accomplished for each section C.sub.i by the calculation:
M'.sub.i =Vd.sub.j (C.sub.i)(modulo N),
where j comprises at least 1, 2, 3, and 4, and where Vd.sub.j is the d.sub.j.sup.th Lucas function with respect to (C.sub.i,1) (modulo N).

### Claim 7

A public key cryptographic system including:
first and second communicating terminals arranged to function respectively as a transmitting and a receiving terminal for electronic signals;
an encoding device at said first terminal and a decoding device at said second terminal;
wherein said encoding device has means for encoding a message to be transmitted by transforming the message with an encryption key including encryption numbers e and N to create an encoded message,
and said decoding device has means for decoding the message by transforming the message with a decryption key using the Lucas functions of the set of numbers D.

### Claim 8

In a method of communicating securely over an insecure communication channel of the type which communicates an electronic signal message from a transmitter to a receiver, the improvement which comprises:
generating a public enciphering key which can be used to encipher messages destined for the receiver, the public enciphering key including two encryption numbers e and N;
generating a secret deciphering key including a set of numbers D for use at the receiver,
by computing the set of numbers D from e and the prime factors of N;
processing the message at the transmitter by:
digitizing said message;
separating said digitized message into sections each comprising a number less than N;
computing a cryptogram section corresponding to each section of the digitized message, using the Lucas function of e to create an enciphered message containing the cryptogram sections;
transmitting the enciphered message;
and processing the enciphered message at the receiver to decode each cryptogram section by transforming them with the Lucas functions of the set of numbers D.

### Claim 9 (depends on 8)

A method as recited in claim 8, further including the steps of:
applying a decoding process to said cryptogram in at least two parts, each said part comprising calculations in respect of one of the prime factors of N;
wherein said parts of the process are performed simultaneously by different decoding apparatus;
and assembling the results of said parts of the process to calculate a decoded message, using the Lucas functions of the set of numbers D.

### Claim 10

A method of providing a digital signature for a communicated electronic signal message comprising the steps of:
providing a public verification key, including two verification numbers e and N;
generating a secret signing key including a set of numbers D wherein the numbers of the set D are derived from e and the prime factors of N such that the secret signing key is directly related to and computationally infeasible to generate from the public verification key;
processing the message to be transmitted and the secret signing key at the transmitter to generate a digital signature at said transmitter by transforming a representation of the message with the secret signing key, by calculating the Lucas function of the set of numbers D such that the digital signature is computationally infeasible to generate from the public verification key;
communicating the public verification key to the receiver;
transmitting the message and the digital signature from the transmitter to the receiver;
receiving the message and the digital signature at the receiver and transforming said digital signature with the public verification key by calculating the Lucas function of e to generate a representation of the message; and
validating the digital signature by comparing the similarity of the message to the representation of the message generated from the digital signature.