×

Public key cryptographic apparatus and method

  • US RE40,530 E1
  • Filed: 10/20/2000
  • Issued: 10/07/2008
  • Est. Priority Date: 12/09/1996
  • Status: Expired due to Term
First Claim
Patent Images

1. A method for establishing cryptographic communications of a message cryptographically processed with RSA (Rivest, Shamir &

  • Adleman) public key encryption, comprising the step steps of;

    developing k distinct random prime numbers p1, p2, . . . , pk, wherein k is an integer greater than 2;

    providing a number e relatively prime to (p1

    1


    (p2

    1


    . . . ·

    (pk

    1
    );

    providing a composite number n equaling the product p1·

    p
    2·

    . . . ·

    p
    k;

    receiving a ciphertext word signal C which is formed by encoding a plaintext message word signal M to a ciphertext word signal C, where M corresponds to a number representative of athe message and
    0≦

    M≦

    n−

    1  

    n being a composite number formed from the product of p1·

    p2·

    . . . ·

    pk where k is an integer greater than 2, p1, p2, . . . pk are distinct prime numbers, and where C is a number representative of an encoded form of the plaintext message word signal M such that
    C≡

    M
    e(mod n)  

    and where e is associated with an intended recipient of the ciphertext word signal C; and

    , wherein said encoding step comprises the step of;

    transforming said message word signal M to said ciphertext word signal C whereby
    C=Me(mod n)  

    where e is a number relatively prime to (p1

    1)·

    (p2

    1). deciphering the received ciphertext word signal C at the intended recipient having available to it the k distinct random prime number p1, p2, . . . pk;

    wherein p and q are a pair of prime numbers that product of which equals a composite number m, the k distinct random prime numbers each smaller than p and q, and the composite number m having the same number of digits as the composite number n;

    wherein the deciphering step is divided into sub-steps, one sub-step for each of the k distinct random prime numbers; and

    wherein for a given number of digits for composite numbers n and m, it takes fewer computational cycles to perform the deciphering step if the k distinct random prime numbers are used, relative to the number of computational cycles for performing a deciphering step if the pair of prime numbers p and q is used instead.

View all claims
  • 4 Assignments
Timeline View
Assignment View
    ×
    ×