KR100844546B1 - Method, system, device for proving the authenticity of an entity or integrity of a message - Google Patents

Abstract

The present invention

secret value Q _i and published value G _i = g _i ² of m (≥1) pairs;

an open module n formed by the product of f (≧ 2) prime factors; And

It relates to a method for verifying by an index v = 2 ^k (k> 1) related to the format G _i Q _i ^v = 1 mod n or G _i = Q _i ^v mod n.

Of the m Q _i obtained by increasing Q _i or the inverse modulo n by the modulus n to the power of modulo n, one of them is not equal to ± g _i . In the 2m equation, where x ² = gi mod n, x ² = -gi mod n, at least one modulo n has a solution in the n integer ring.

Module, authenticity, integrity, validation, entity

Description

METHOD, SYSTEM, DEVICE FOR PROVING THE AUTHENTICITY OF AN ENTITY OR INTEGRITY OF A MESSAGE}

The present invention relates to methods, systems, and apparatuses for verifying the authenticity of an entity and / or the integrity and / or authenticity of a message.

EP O 311 470 B1 (inventor; Louis Guillou and Jean-Jacques Quisquater) describes this method. Hereinafter, the patent will be referred to using the terms "GQ patent" or "GQ method". In addition, hereinafter, to describe the present invention, the expression "GQ2" or "GQ2 invention" or "GQ2 technique" will be used.

According to the GQ technique, an entity known as a "trusted authority" assigns an identity to each entity called "witness" and computes its RSA signature. In the customization process, the trusted authority gives the witness identification information and signature. The witness then declares, "Here is my identifying information. I know the RSA signature of the identifying information." The witness certifies that he knows the RSA signature of the identifying information without revealing the RSA signature. An entity known as a "controller" via an RSA public identification key distributed by a trusted authority does not receive knowledge of the identification key and verifies that the RSA signature matches the declared identification. . The mechanism using the GQ technique is done "without knowledge transfer." According to the GQ technique, the witness does not know the RSA secret key that a trusted authority uses to sign a lot of identifying information.

The GQ technique described above uses RSA technology. However, while the RSA technique depends precisely on the factorization of modulus n, this dependency is not the same. In other words, it is actually different, as is shown in the so-called "multiplicative attack" against the various standards of digital signatures that implement RSA technology.

The purpose of the GQ2 technique is twofold. One is to improve the inherent performance of the RSA technology, and the other is to solve the inherent problems of the RSA technique. The knowledge of the GQ2 secret key is equivalent to the knowledge of the factorization of modulus n. Any attack on the triplet GQ2 is also factored on modulus n. This time is equivalent. By using the GQ2 technique, the workload is reduced for signature or self-certifying entities and control entities. By making better use of factorization issues in terms of security and performance, the GQ2 technique overcomes the shortcomings of the RSA technique.

The GQ technique implements a number of modulo operations of more than 512 bits. The arithmetic value is associated with a number that is substantially the same size as the magnitude raised to the power of 2 ¹⁶ +1 order. However, in the field of bank cards, existing microelectronic infrastructures use monolithic self-programmable microprocessors without computational coprocessors. Workloads associated with multi-computation applications belonging to the same method as the GQ technique cause computation time, which in some cases makes the consumer uncomfortable paying with a bank card at the time of purchase. It is conceivable here that in improving the security of payment cards, banks may face problems that are particularly difficult to solve. Indeed, two obviously contradictory problems must be solved. That is to say, on the one hand, increasingly long and clear keys are used for each card to increase security, while on the other hand, the workload should not cause excessive computation time for the user. This problem is aggravating and it is therefore necessary to consider current infrastructure and microprocessors.

The GQ2 technique aims to enhance security and at the same time provide a solution to the above problems.

Way

More specifically, the present invention relates to a controller entity,

The authenticity of the entity and / or

A verification method for verifying the integrity of message M associated with an entity.

This verification is

m pairs of secret values Q ₁ , Q ₂ , ..., Q _m and the public values G ₁ , G ₂ , ..., G _m (m is 1 or more),

a parameter comprising a public modulus n (f is greater than or equal to 2) composed of the product of _f prime factors P ₁ , P ₂ , ..., P _f , and some or all of its derivatives .

Modulus, secret and open values are G _i × Q _i ^v = 1 mod n or G _i = Q _i ^v mod n, where v is a public index of the form v = 2 ^k , where k is a security parameter greater than 1

m public values G _i is the squared g _i ² of _m base numbers g ₁ , g ₂ , ..., g _m less than f prime factors p ₁ , p ₂ , ..., p _m , The f prime factors p ₁ , p ₂ , ..., p _f and / or the m base numbers g ₁ , g ₂ , ..., g _m are multiplied to satisfy the following conditions.

First condition

x _v = g _i ² mod n (1)

Each of the above expressions can be solved with x in the integer ring of modulo n.

Second condition
If G _i = Q _i ^v mod n, then among m m q _i obtained by squaring Q _i and taking modulo n k-1 times, one of them is not equal to ± g _i (i.e. no.)

delete

If, when G _i Q _i ^v = 1 a mod n, from the m number q _i is obtained by taking the n time k-1 to the station module of what the squares of n modulo of Q _i, one of them is ± g _i, and Not equal (ie not simple)

Third condition

x ² = g _i mod n (2)

x ² =-g _i mod n (3)

At least one of the 2m equations can be solved by x in an integer ring of modulo n.

The method implements, in the next step, an entity called a witness (witness), the entity having f prime factors p _i and / or m radix g _i and / or parameters of the difference surplus value of the prime factors and / or public modulus n and / or the m secret values Q _i and / or the secret values Q _i and the f × m components Q _{i, j} (Q _{i, j} = Q _i mod p _j ) of the public index v At least one.

The witness computes a commitment R on the integer ring of modulo n. Where each commitment is:

R is any value where r is 0 <r <n = r ^v mod n or

r _i is a random value associated with the prime number P _i , where 0 <r _i <p _i and each r _i is in the collection of random values {r ₁ , r ₂ , ..., r _f } R _i = r _i ^v It is calculated by executing the operation of mod p _i and then applying the Chinese remaninders method.

The witness receives one or more challenges d, each including an integer d _i called m initial challenges. Its witness is based on each challenge, d = r × Q ₁ ^d ₁ × Q ₂ ^d ₂ × ... × Q _m ^dm Perform the operation of mod n or D _i = r _i × Q _{i, 1} ^d1 × Q _{i, 2} ^d2 × ... × Q _{i, m} ^dm Calculate the response D by executing the operation of mod p _i and then applying the Chinese remainder method.

The method allows the response D to be equal in number to the challenge d and the commitment R so that the groups of R, d, and D form a triplet referred to as {R, d, D}.

When verifying the authenticity of an entity

According to the first embodiment, the verification method according to the present invention verifies the authenticity of an entity known as an authenticator to an entity known as a controller. The attestor entity includes the attestor.

The prover and controller,

Phase 1: Commitment of Commitment R

At each call, the witness calculates each commitment R by applying the procedure described in paragraph 1,

The prover sends some or all of each commitment R to the controller.

Phase 2: Actions of Challenge d

After the controller receives some or all of commitment R, the controller generates the same number of challenges d as the number of commitments R and sends the challenge d to the prover.

Phase 3: Response D's Action

The witness calculates the response D from the challenge d by applying the procedure described in claim 1.

ㆍ Step 4: Inspection Act

The attestor executes sending each response D to the controller.

Case 1: If the prover sent a portion of each commitment R

If the prover sent a portion of each commitment R, the controller with m public values G ₁ , G ₂ , ..., G _m calculates the reconstructed commitment R 'from each challenge d and each response D and , The reconstructed commitment R '

R '= G ₁ ^d ₁ × G ₂ ^d ₂ × ... × G _m ^dm × D ^v mod n, or

R '= D ^v / G ₁ ^d1 × G ₂ ^d2 × ... × G _m ^dm × D ^v mod n is satisfied.

The controller confirms that each reconstructed commitment R 'regenerates some or all of each commitment R that was sent to that controller.

Case 2: if the prover sent all of each commitment R

If the proving party transmits the whole of each of the commitment R, of m public values G _1, G _2, ..., each of said control characters having a commitment R _m G is

R = G ₁ ^d ₁ × G ₂ ^d ₂ × ... × G _m ^dm × D ^v mod n, or

R = D ^v / G ₁ ^d1 × G ₂ ^d2 × ... × G _m ^dm mod n Check if the equation is satisfied.

When verifying the integrity of a message

In a second embodiment, which can be combined with the first embodiment, the method according to the invention is designed to verify the integrity of a message M associated with an entity known as a prover entity to an entity known as a controller entity. The attestor entity includes the attestor.

The prover and controller entity,

Phase 1: Commitment of Commitment R

At each call, the witness calculates each commitment R using the procedure described in claim 1.

Phase 2: Actions of Challenge d

The prover calculates at least one token T by applying a hashing function h whose argument is message M and all or part of each commitment R. The prover sends the token T to the controller. After receiving the token T, the controller generates a challenge d with the same number of commitments R and sends the challenge d to the prover.

Phase 3: Response to Response D

The witness applies the procedure described in claim 1 to calculate the response D from the challenge d.

ㆍ 4th step: inspection

The prover sends each response D to the controller. The controller with m public values G ₁ , G ₂ , ..., G _m reconstructs each commitment R 'from each of challenge d and response D, and the reconstructed commitment R'

R '= G ₁ ^d ₁ × G ₂ ^d ₂ × ... × G _m ^dm × D ^v mod n, or

R '= D ^v / G ₁ ^d1 × G ₂ ^d2 × ... × G _m ^dm mod n

The controller then reconstructs at least one token T 'by applying a hashing function h whose argument is message M and all or part of each reconstructed commitment R'.

The controller executes a step of checking whether the token T 'is the same as the transmitted token T'.

Digital signature of the message and proof of its authenticity

In a third embodiment according to the invention, which can be combined with the two preceding embodiments, the method according to the invention is designed for generating a digital signature of message M by an entity known as a signing entity. The signing entity includes the attestor.

Signature

The signature entity is

Message M

Challenge d and / or commitment R

Response D

Performs a signature operation to obtain a signed message including

The signature entity

Phase 1: Commitment of Commitment R

At each call, the witness applies the procedure described in claim 1 to calculate each commitment R.

Phase 2: Actions of Challenge d

The signer obtains a binary train by applying a hashing function h whose argument is message M and all or part of each commitment R. From this binary train the signer comprises extracting the challenge d in the same number as the number of commitments R.

Phase 3: Response to Response D

The witness performs the signature operation by implementing the step of calculating the response D from the challenge d by applying the procedure described in claim 1.

Inspection works

To verify the authenticity of message M, an entity called a controller examines the signed message. The controller entity with the signed message is

The controller has commitment R, challenge d and response D.

When the controller has a commitment R, a challenge d, and a response D, the controller has a commitment R, a challenge d, a response D where R = G ₁ ^d1 x G ₂ ^d2 x ... x G _m ^dm x D ^v Check whether mod n or R = D ^v / G ₁ ^d1 × G ₂ ^d2 × ... × G _m ^dm mod n is satisfied. The controller checks if message M, challenge d and commitment R satisfy the hashing function d = h (message, R).

The controller has a challenge d and a response D.

If the controller has a challenge d and response D, the controller is based on each challenge d and response D, and R '= G ₁ ^d ₁ × G ₂ ^d ₂ × ... × G _m ^dm × D ^v mod n or R '= D ^v / G ₁ ^d1 × G ₂ ^d2 × ... × G _m ^dm Recommit the commitment R 'that satisfies the relation of mod n. The controller checks whether the message M and the challenge d satisfy a hashing function d = h (message, R ').

The controller has commitment R and response D.

If the controller has a commitment R and a response D, the controller reconstructs d 'by applying a hashing function d' = h (message, R), and the controller has a sinker commitment R and the challenge d 'and the response. The formula D is R = G ₁ ^d1 × G ₂ ^d2 × ... × G _m ^dm × D ^v mod n or R = D ^v / G ₁ ^d1 × G ₂ ^d2 × ... × G _m ^dm mod n Perform the check operation by the procedure to check if

system

The invention also relates to a controller server

The authenticity of the entity or (and)

A verification system for verifying the integrity of message M associated with said entity.

This verification is established by some or all of the following parameters and their derivatives.

m pairs of secret values Q ₁ , Q ₂ , ..., Q _m and the public values G ₁ , G ₂ , ..., G _m (m is 1 or more),

-the open modulus n composed of the product of _f prime factors p ₁ , p ₂ , ..., p _f (f is not less than 2)

The modulus, the secret value and the published value are G _i × Q _i ^v = 1 mod n or G _i = Q _i ^v mod n, where v is a public index of the form v = 2 ^k , where k is a security parameter greater than 1

The m public values G _i is f of prime factors p _1, p _2, ..., smaller than radix p _f g _1, g the power of _{2, ..., g m g i} 2,

The prime factors p ₁ , p ₂ , ..., p _f and / or the m base numbers g ₁ , g ₂ , ..., g _m are multiplied to satisfy the following conditions.

First condition

x _v = g _i ² mod n (1)

Each of the above expressions can be solved with x in the integer ring of modulo n.

Second condition

If G _i = Q _i ^v mod n, one of them is not equal to ± g _i (ie, not simple) out of m q _i obtained by taking n−1 with Q _i squared modulus. )

If G _i Q _i ^v = 1 mod n, then among m m q _i obtained by taking n inverse squared modulo n of Q _i modulo, one of them is ± g _i and Not equal (Ie not simple)

Third condition

x ² = g _i mod n (2)

x ² =-g _i mod n (3)

At least one of the 2m equations can be solved by x in an integer ring of modulo n.

The system also includes in particular a witness device embedded in a nomad object, for example in the form of a microprocessor based bank card.

The attestation apparatus may include a parameter of the f prime factor p _i and / or m base numbers g _i and / or the prime surplus value and / or the public modulus n and / or the m secret values Q _i and / or its secrets. F x m components of the value Q _i and its open index v Q _{i, j} (Q _{i, j} = Q _i mod p _j ) It includes a memory area including a.

The witness apparatus is hereinafter referred to as random value generating means, called means for generating a random value of the witness apparatus, and

Calculation means for calculating the commitment R in the integer ring of modulo n, referred to below as means for calculating the commitment R of the witness apparatus.

The calculation means makes it possible to calculate the commitment R at the integer ring of modulo n. Each commitment R is

r is a random value where 0 <r <n = r ^v perform an operation of mod n, or r _i is a random value associated with prime number P _i such that 0 <r _i <p _i and each r _i is a collection of random values {r ₁ , r ₂ , ..., r _f } If it belongs to R _i = r _i ^v Perform the operation of mod p _i and then calculate it by applying the Chinese residual surplus method.

In addition, the witness apparatus,

Receiving one or more challenges d, hereinafter referred to as means for receiving a challenge d of the witness apparatus, each challenge d comprising m integers d _i (also called initial challenges),

Responsive D is defined based on each challenge d, which is hereafter referred to as the means for calculating the response D of the witness device, where D = r x Q ₁ ^d ₁ Q ₂ ^d ₂ x ... x Q _m ^dm mod n Calculation by executing the calculation or by performing the calculation of D = r × Q _{i, 1} ^d1 × Q _{i, 2} ^d2 × ... × Q _{i, m} ^dm mod p _i Calculation means for calculating.

The attestation device also includes transmission means for transmitting one or more of the challenge d and one or more response D. The response D is present in the same number as each commitment R and challenge R, and the groups of R, d and D form a triplet referred to as {R, d, D}.

When verifying the authenticity of an entity

In the first embodiment, the system according to the present invention verifies the authenticity of an entity called the prover and the entity called the controller.

The system is interconnected with the attestation device by means of interconnecting means, in particular a prover device associated with an attestor entity, in the form of a logic microcircuit of a nomad object, for example a microprocessor form of a microprocessor-based bank card, And, in particular, in the form of a terminal or remote server, connecting means for connecting to the prover device electronically, electromagnetically, optically or phonetically, in particular connecting means such as a data processing communication network. And a controller device associated with the controller.

The system,

Phase 1: Commitment of Commitment R

At each call, the commitment R calculation means of the attestor apparatus calculates each commitment R by applying the procedure described in claim 1, and the attestor apparatus is configured to communicate each of the commitments R to the prover apparatus via the interconnecting means. A transmission means for transmitting part or all of the following, hereinafter referred to as transmission means of the witness apparatus,

The prover device has transmission means for transmitting a part or all of each of the commitments R to the controller device via the connection means, hereinafter referred to as transmission means of the prover device.

Phase 2: Actions of Challenge d

The controller device comprises challenge generating means for generating a challenge d with a number equal to the number of commitments R after receiving some or all of each of the commitments R, and wherein the controller device via the connection means And a transmission means for transmitting the challenge d to the prover, hereinafter referred to as a transmission means of the controller.

Phase 3: Response to Response D

The challenge d receiving means of the attestation device receives each challenge d coming from the prover device through the interconnecting means, and the response D calculation means of the attestation device applies the procedure described in claim 1 to the challenge. The response D is calculated from d.

ㆍ 4th step: inspection

The transmission means of the prover sends each response D to the controller,

In addition, the controller device

Calculation means hereinafter referred to as calculation means of the controller device;

Enabling the execution of steps comprising comparison means, hereinafter referred to as comparison means of the controller device.

If the prover sent a portion of each commitment R.

If the prover's transmitting means has transmitted a portion of each commitment R, then the computing means of the controller device with _m public values G ₁ , G ₂ ,..., G _m is calculated from each challenge d and each response D. Calculate the reconstructed commitment R ', wherein the reconstructed commitment R' is the formula of R '= G ₁ ^d1 × G ₂ ^d2 × ... × G _m ^dm × D ^v mod n, or R' = D ^v / G ₁ ^d1 x G ₂ ^d2 x ... x G _m ^dm mod n, where the comparing means of the controller device compares each or all of the already received commitments R with each reconstructed commitment R '.

If the prover sent all of its commitments R.

If the transmitting means of the prover has transmitted all of the commitments R, the calculating means and the comparing means of the controller apparatus having _m public values G ₁ , G ₂ ,. Satisfies the formula G ₁ ^d1 × G ₂ ^d2 × ... × G _m ^dm × D ^v mod n, or R = D ^v / G ₁ ^d1 × G ₂ ^d2 × ... × G _m ^dm mod n Check if

When verifying the integrity of a message

In a second embodiment, which may be combined with the first embodiment, the system according to the invention allows an entity known as the controller entity to give witnesses of the integrity of the message M associated with the entity called the prover entity. The system is associated with the attestor device by interconnecting means, and may be in the form of a logic microcircuit of a nomad object, for example a microprocessor form of a microprocessor-based bank card. And, in particular in the form of a terminal or a remote server, the controller comprising connecting means for connecting the prover device electronically, electromagnetically, optically or phonetically, in particular connecting means such as a data processing communication network. It is made to include a controller device associated with the entity.

The system                 

Phase 1: Commitment of Commitment R

At each call, the commitment R calculation means of the attestation device calculates each commitment R by applying the procedure described in claim 1, wherein the attestation device is connected to the attestor device via the interconnecting means. And a transmission means for transmitting part or all, hereinafter referred to as a transmission means of the witness apparatus.

Phase 2: Actions of Challenge d

The prover device comprises calculation means for calculating at least one token T by applying a message M and a hashing function h, which is all or part of each commitment R, hereinafter referred to as the calculation means of the prover; ,

In addition, the prover device includes a transmission means for transmitting each token T to the controller device through the connection means, hereinafter referred to as a transmission means of the prover device,

Furthermore, the controller device includes a challenge generating means for generating a challenge d with a number equal to the number of commitments R after receiving the token T,

The controller device also includes a transmission means for transmitting the challenge d to the prover via the connection means, hereinafter referred to as the transmission means of the controller.

Phase 3: Response to Response D

The challenge d receiving means of the attestation device receives each challenge d coming from the prover device through the interconnecting means, and the response D calculating means of the attestation device applies the procedure described in claim 1 to the The response D is calculated from the challenge d.

ㆍ 4th step: inspection

The transmitting means of the prover transmits each response D to the controller.

Further, the controller device first has m public values G ₁ , G ₂ ,..., G _m , reconstructs each commitment R ′ from each of the challenge d and the response D, and the reconstructed commitment R Where R '= G ₁ ^d1 × G ₂ ^d2 × ... × G _m ^dm × D ^v mod n, or R' = D ^v / G ₁ ^d1 × G ₂ ^d2 ... G _m ^dm mod n Calculate whether the equation is satisfied.

Calculation means for calculating at least one token T 'by applying a hashing function h, whose argument is all or part of message M and each reconstructed commitment R', hereinafter referred to as calculation means of the controller device. It includes.

The controller device also makes it possible to carry out a step comprising comparing means for comparing the token T 'with the transmitted token T, hereinafter referred to as comparing means of the controller device.

Digital signature of the message and verification of its authenticity

In a third embodiment according to the invention, which can be combined with each other or with the above embodiments, the system according to the invention is a message M-hereinafter referred to as a signed message-by an entity called a signing entity. To verify the digital signature.

The signature message is,                 

-Message M,

Challenge d and / or commitment R,

-Include response D.

Signature works

The system is interconnected with the attestation device by means of interconnecting means, in particular a signature device associated with the signature entity, which may be in the form of a logic microcircuit of a nomad object, for example a microprocessor of a microprocessor-based bank card. signing device).

The system is used to perform the following steps.

Phase 1: Commitment of Commitment R

At each call, the commitment R calculation means of the attestation device calculates each commitment R by applying the procedure described in claim 1, wherein the attestation device is said to commit each R to the prover device via the interconnecting means. A transmission means for transmitting part or all of the following, hereinafter referred to as transmission means of the witness apparatus.

Phase 2: Actions of Challenge d

The signature apparatus calculates a binary train by applying a hashing function h whose argument is all or part of the message M and each commitment R, and calculating means for extracting the challenge d from the binary train by the same number as the number of commitment Rs. Hereinafter referred to as the calculation means of the signature device.

Phase 3: Response to Response D

The challenge d receiving means of the attestation device receives each challenge d coming from the prover device through the interconnecting means, and the response D calculating means of the attestation device applies the procedure described in claim 1 to the challenge. Compute the response D from d, wherein the attestation device comprises transmission means for transmitting the response D to the signature device via the interconnecting means.

Inspection works

The system verifies the authenticity of the message M by an entity known as a controller checking the signed message.

The system is in the form of a terminal or a remote server, in particular, the controller having connection means for connecting the signature device electronically, electromagnetically, optically or phonetically, in particular a connection such as a data processing communication network. It includes a controller device associated with the entity.

The signature device associated with the signature entity includes transmission means for transmitting a message signed through the connection means to the controller device, hereinafter referred to as transmission means of the signature device.

In this way, the controller device

-Message M,

Challenge d and / or commitment R,

You have a signed message that contains Response D.                 

The controller device,

Calculating means, hereinafter referred to as calculating means of the controller device;

Comparison means, hereinafter referred to as comparison means of the controller device.

If the controller device has commitment R, challenge d, response D

When the controller device has a commitment R, a challenge d and a response D, the calculation means and the comparison means of the controller device have a commitment R, a challenge d and a response D equal to R = G ₁ ^d1 × G ₂ ^d2 ×. Verify that the equation of G _m ^dm × D ^v mod n or R = D ^v / G ₁ ^d1 × G ₂ ^d2 × ... × G _m ^dm mod n is satisfied.

Subsequently, the calculating means and the comparing means of the controller device check whether the message M, the challenge d, and the commitment R satisfy the hashing function d = h (message, R).

When controller device has challenge d and response D

When the controller device has a challenge d, a response D, the controller's calculation means is based on each challenge d and the response D, where R '= G ₁ ^d1 × G ₂ ^d2 × ... × G _m ^dm × D ^v mod n, or R '= D ^v / G ₁ ^d1 × G ₂ ^d2 × ... × G _m ^dm Reconstruct the commitment R 'that satisfies the expression of mod n.

Subsequently, the calculating means and the comparing means of the controller device check whether the message M and the challenge d satisfy a hashing function d = h (message, R ').

The controller device has a commitment R and a response D.

When the controller device has a commitment R and a response D, the calculating means of the controller device calculates d 'by applying a hashing function d' = h (message, R).

Subsequently, the calculation means and the comparison means of the controller apparatus include a synchronizing commitment R and the challenge d 'and the response D, wherein R = G ₁ ^d'1 × G ₂ ^d'2 × ... × G _m ^d'm. Verify that the expression x D ^v mod n or R = D ^v / G ₁ ^d'1 x G ₂ ^d'2 x ... x G _m ^d'm mod n is satisfied.

Terminal device

The invention also relates to a terminal device associated with an entity.

The terminal device is, in particular, in the form of a microprocessor based bank card, for example in a nomad object. The terminal device tells the controller server

The authenticity of the entity and / or

Designed to verify the integrity of message M associated with the entity.

This verification is

m pairs of secret values Q ₁ , Q ₂ , ..., Q _m and the public values G ₁ , G ₂ , ..., G _m (m is 1 or more),

-is established by a parameter of open module n (f is greater than or equal to 2) composed of the product of _f prime factors p ₁ , p ₂ , ..., p _f and some or all of its derivatives.

The module, the secret value and the published value are G _i × Q _i ^v = 1 mod n or G _i = Q _i ^v mod n, where v is a public index of the form v = 2 ^k , where k is a security parameter greater than one.

The m public values G _i is f of prime factors p _1, p _2, ..., smaller than radix p _f g _1, g the power of _{2, ..., g m g i} 2, the prime factor p _1, p ₂ , ..., p _f and / or the m base numbers g ₁ , g ₂ , ..., g _m are multiplied to satisfy the following conditions.

First condition

x _v = g _i ² mod n (1)

Each of the above expressions can be solved with x in the integer ring of modulo n.

Second condition

If G _i = Q _i ^v mod n, one of them is not equal to ± g _i (ie, not simple) out of m q _i obtained by taking n−1 with Q _i squared modulus. )

If G _i Q _i ^v = 1 mod n, then among m m q _i obtained by taking n inverse squared modulo n of Q _i modulo, one of them is ± g _i and Not equal (ie not simple),

Third condition

x ² = g _i mod n (2)

x ² =-g _i mod n (3)

At least one of the 2m equations can be solved by x in an integer ring of modulo n.

The terminal device may include a parameter of f prime factors p _i and / or m radix g _i and / or the difference surplus value of the prime factors and / or the public modulus n and / or the m secret values Q _i and / or its secrets. A witness device having a memory area comprising a value Q _i and f × m components Q _{i, j} (Q _{i, j} = Q _i mod p _j ) of its public index v.

The attestation apparatus further includes random value generating means, hereinafter referred to as means for generating a random value of the witness apparatus, and calculation means hereinafter, means for calculating the commitment R of the attestation apparatus. The calculation means calculates a commitment R in a ring of integer modulo n.

Each commitment R is

R is any value where r is 0 <r <n = r ^v mod n or

r _i is a random value associated with the prime number P _i , where 0 <r _i <p _i and each r _i is a collection of random values produced by the random value generating means {r ₁ , r ₂ , ..., r _f } If it belongs to R _i = r _i ^v Perform the operation of mod p _i and then apply the Chinese difference surplus method.

In addition, the witness apparatus,

Receiving means comprising at least one challenge d, each challenge d comprising m integers d _i (also called initial challenges), hereinafter referred to as means for receiving a challenge d of the witness device;

Response D, based on each challenge d,

D = r × Q ₁ ^d1 × Q ₂ ^d2 × ... × Q _m ^dm perform a mod n operation, or

D = r × Q _{i, 1} ^d1 × Q _{i, 2} ^d2 × ... × Q _{i, m} ^dm calculation means for executing the calculation of mod p _i and then applying the difference surplus method, hereinafter referred to as means for calculating the response D of the witness apparatus.

The attestation device comprises transmission means for transmitting the one or more commitments R and one or more response Ds. The response D is present in the same number as each commitment R and the challenge d, and each group of R, d, D forms a triplet referred to as {R, d, D}.

For verification of the authenticity of an entity

In the first embodiment, the terminal device according to the present invention verifies the authenticity of an entity called an authenticator to an entity called a controller.

The terminal device is associated with the attestor entity and is interconnected with the attestation device by interconnecting means. In particular, it includes a prover device that can be in the form of a logic microcircuit in a nomad object, for example in the form of a microprocessor of a microprocessor-based bank card.

The prover device also comprises connecting means for connecting the controller device electronically, electromagnetically, optically or phonetically, in particular connection means such as a data processing communication network. It may be in the form of a terminal or a remote server.

The terminal device is used to perform the following steps. ,

Step 1: Action of Commitment R

At each call, the commitment R calculation means of the attestation device calculates each commitment R by applying the procedure described in claim 1, wherein the attestation device is said to commit each R to the prover device via the interconnecting means. A transmission means for transmitting part or all of the following, hereinafter referred to as transmission means of the witness apparatus.

Further, the prover device has a transmission means for retransmitting part or all of each of the commitments R to the controller device via the connection means, hereinafter referred to as transmission means of the prover device.

Second and Third Steps: Challenge d, Response D's Action.

The challenge d receiving means of the attestor device receives each challenge d coming from the attestor device through a connecting means between the controller device and the prover device and an interconnecting means between the prover device and the attestation device. Upon receipt, the response D calculation means of the attestation device calculates the response D from the challenge d by applying the procedure described in claim 1 above.

ㆍ 4th step: inspection

The sending means of the prover sends each response D to the controller executing the inspection.

For the verification of the integrity of the message

In a second embodiment, which can be combined with the first embodiment, the terminal device is subject to an entity known as the controller entity to the verification of the integrity of the message M associated with the entity called the prover entity.

The terminal device is configured to include an authenticator device associated with the attestor entity, wherein the prover device is connected to the attestor device by interconnection means, the prover device being in particular a logic microcircuit in the nomad object. It may be in the form of, for example, a microprocessor of a microprocessor-based bank card.

 The prover device comprises connecting means for connecting electronically, electromagnetically, optically or phonetically with the controller device associated with the controller entity, in particular connecting means such as a data processing communication network, in particular the controller The device may be in the form of a terminal or a remote server.

The terminal device is used to perform the following steps.

Phase 1: Commitment of Commitment R

At each call, the commitment R calculation means of the attestation device calculates each commitment R by applying the procedure described in claim 1, wherein the attestation device is part of the commitment R to the prover device via the interconnecting means. Or a transmission means for transmitting the whole, hereinafter referred to as a transmission means of the witness apparatus.

2nd and 3rd stage: challenge d action, response D action

The prover device includes calculation means for calculating at least one token T by applying a hashing function h whose argument is the message M and all or part of each commitment R, hereinafter referred to as the calculation means of the prover. . Further, the prover device has a transmission means for transmitting each token T to the controller device through the connection means, hereinafter referred to as a transmission means of the prover device.

The controller device generates a challenge d with a number equal to the number of commitments R after receiving the token T.

The challenge d receiving means of the at least one witness device receives each challenge d coming from the controller device through a connecting means between the controller device and the prover device and an interconnecting means between the prover device and the attestation device. do.

The response D calculation means of the witness apparatus calculates the response D from the challenge d by applying the procedure described in claim 1.

ㆍ 4th step: inspection

The sending means of the prover sends each response D to the controller device, which executes the inspection.

Digital signature of the message and verification of its authenticity

In a third embodiment, which can be combined with any of the two embodiments, the terminal device verifies the digital signature of the message M, hereafter referred to as a signed message, by an entity called a signing entity.

The signature message is,

-Message M,

Challenge d and / or commitment R,

-Include response D.

The terminal device is configured to include a signature device associated with the signer entity. The signature device is interconnected with the attestation device by means of interconnection means and may also be in the form of a logic micro circuit, in particular in a nomad object, for example in the form of a microprocessor of a microprocessor based bank card.

The signature device comprises connecting means for connecting electronically, electromagnetically, optically or phonetically with the controller device associated with the controller entity, in particular connection means such as a data processing communication network, the controller device being a terminal. Or in the form of a remote server.                 

Signature works

The terminal device is used to perform the following steps.

Step 1: Action of Commitment R

At each call, the commitment R calculation means of the attestation device calculates each of the commitments R by applying the procedure described in claim 1 above. The attestation device has a transmission means for transmitting some or all of each commitment R to the attestor device via the interconnecting means, hereinafter referred to as a transmission means of the attestation device.

Phase 2: Actions of Challenge d

The signature apparatus calculates a binary train by applying a hashing function h whose argument is all or part of the message M and each commitment R, and calculating means for extracting the challenge d from the binary train by the same number as the number of commitment Rs. Hereinafter referred to as the calculation means of the signature device.

Phase 3: Response to Response D

The challenge d receiving means of the attestation device receives each challenge d coming from the signature device via the interconnecting means. The response D calculation means of the witness apparatus calculates the response D from the challenge d by applying the procedure described in claim 1. The attestation device comprises a transmission means for transmitting the response D to the signature device via the interconnecting means, hereinafter referred to as a transmission means of the attestation device.

Controller device

The invention also relates to a controller device. The controller device in particular takes the form of a terminal or a remote server associated with the controller entity. The controller device

The authenticity of the entity and / or

Verify the integrity of message M associated with the entity.

This verification is established by some or all of the following parameters and their derivatives.

m pairs of public values G ₁ , G ₂ , ..., G _m (m is 1 or more),

a public modulus n consisting of the product of _f prime factors p ₁ , p ₂ , ..., p _f , unknown to the controller device and its associated controller entity, where f is 2 or more

The modulus, the secret value and the published value are G _i × Q _i ^v = 1 mod n or G _i = Q _i ^v mod n, where v is a public index of the form v = 2 ^k , where k is a security parameter greater than one.

The m public values G _i is f of prime factors p _1, p _2, ..., smaller than radix p _f g _1, g the power of _{2, ..., g m g i} 2, the prime factor p _1, p ₂ , ..., p _f and / or the m base numbers g ₁ , g ₂ , ..., g _m are multiplied to satisfy the following conditions.

First condition

x _v = g _i ² mod n (1)

Each of the above expressions can be solved with x in the integer ring of modulo n.

Second condition

If G _i = Q _i ^v mod n, one of them is not equal to ± g _i (ie, not simple) out of m q _i obtained by taking n−1 with Q _i squared modulus. )

If G _i Q _i ^v = 1 mod n, then among m m q _i obtained by taking n inverse squared modulo n of Q _i modulo, one of them is ± g _i and Not equal (i.e. not simple)

Third condition

x ² = g _i mod n (2)

x ² =-g _i mod n (3)

At least one of the 2m equations can be solved by x in an integer ring of modulo n.

When verifying the authenticity of an entity

In a first embodiment, the controller device according to the present invention verifies the authenticity of an entity called a controller and an entity called an authenticator.

The controller device comprises connecting means for connecting electronically, electromagnetically, optically or phonetically with the prover device associated with the prover entity, in particular connection means such as a data processing communication network.

The controller device is used to perform the following steps.

Steps 1 and 2: Act of Commitment R, Act of Challenged

The controller device also has receiving means for receiving some or all of the commitment R coming from the prover device via the connecting means.

The controller device comprises challenge generating means for generating a challenge d with a number equal to the number of commitments R after receiving some or all of each prover R, wherein each challenge d is referred to as m initial challenges. Contains the integer d _i .

The controller device also includes a transmission means for transmitting the challenge d to the prover via the connection means, hereinafter referred to as the transmission means of the controller.

ㆍ 3rd and 4th Stage: Response and Response of Response D

The controller device

Receiving means for receiving a response D from the prover device via the interconnecting means;

Calculating means, hereinafter referred to as calculating means of the controller device;

Comparison means, hereinafter referred to as comparison means of the controller device.

First case: If the prover sent a portion of each commitment R

If the prover's transmitting means has transmitted a portion of each commitment R, then the computing means of the controller device having _m public values G ₁ , G ₂ ,..., G _m is calculated for each challenge d and each response D. Calculate the reconstructed commitment R 'from the reconstructed commitment R'

R '= G ₁ ^d1 × G ₂ ^d2 × ... × G _m ^dm XD ^v mod n,

Or R '= D ^v / G ₁ ^d1 × G ₂ ^d2 × ... × G _m ^dm The expression of mod n is satisfied.

The comparing means of the controller device compares each or all of the received commitments R with each reconstructed commitment R '.

Case 2: if the prover sent all of each commitment R

If the transmitting means of the prover has transmitted all of the commitments R, the calculating means of the controller device having _m public values G ₁ , G ₂ ,.

R = G ₁ ^d1 × G ₂ ^d2 × ... × G _m ^dm XD ^v mod n, or

R = D ^v / G ₁ ^d1 × G ₂ ^d2 × ... × G _m ^dm Check that mod n's expression is satisfied.

When verifying the integrity of a message

In a second embodiment, which can be combined with the first embodiment, the controller device according to the present invention verifies the integrity of the message M associated with an entity known as the controller.

The controller device comprises connecting means for connecting electronically, electromagnetically, optically or phonetically with the prover device associated with the prover entity, in particular connection means such as a data processing communication network.

The system is used to perform the following steps.

Phases 1 and 2: Act of Commitment R, Act of Challenge d

The controller device has means for receiving a token T coming from the prover device via the connecting means. The controller device has a challenge generating means for generating a challenge d with a number equal to the number of commitments R after receiving the token T, each challenge d including m integers called an initial challenge d _i . The controller device also includes a transmission means for transmitting the challenge d to the prover via the connection means, hereinafter referred to as the transmission means of the controller.

Third and Fourth Steps: Response and Investigations of Response D

The controller device comprises means for receiving each challenge d coming from the prover device via the connecting means.

The controller device first has m public values G ₁ , G ₂ ,..., G _m , and expresses a commitment R 'reconstructed from each of the challenge d and the response D, where R' = G ₁ ^d1 × G _2. ^d2 × ... × G _m ^dm × D ^v mod n, or the formula R '= D ^v / G ₁ ^d1 × G ₂ ^d2 × ... × G _m ^dm Calculate to satisfy the expression of mod n, and then apply the hashing function h whose argument is all or part of message M and each of the reconstructed commitments R 'to calculate at least one token T', Calculation means called calculation means of the controller device.

The controller device also includes comparing means, hereinafter referred to as comparing means of the controller device, for comparing the token T 'with the transmitted token T'.

Digital signature of the message and verification of its authenticity

In a third embodiment, which can be combined with the above embodiments, the controller device according to the invention checks the authenticity of message M by checking a message signed by an entity called a signed message.

The signed message, sent by the signature device associated with the signature entity with a hashing function h (message, R),

-Message M,

Challenge d and / or commitment R,

-Include response D.

Inspection

The controller device comprises connecting means for connecting electronically, electromagnetically, optically or phonetically with a signature device associated with the signature entity, in particular connection means such as a data processing communication network, the controller device comprising the connection. Receive a signed message from the signing device via the means.

The controller device

Calculating means, hereinafter referred to as calculating means of the controller device;

Comparison means, hereinafter referred to as comparison means of the controller device.

If the controller device has commitment R, challenge d, response D:

If the controller device has a commitment R, a challenge d and a response D, the calculation means and the comparison means of the controller device indicate that the commitment R, the challenge d and the response D are

R = G ₁ ^d1 × G ₂ ^d2 × ... × G _m ^dm × D ^v mod n or

R = D ^v / G ₁ ^d1 × G ₂ ^d2 × ... × G _m ^dm Verify that the formula mod n is satisfied.

Subsequently, the calculating means and the comparing means of the controller device check whether the message M and the challenge d satisfy the hashing function d = h (message, R).

The controller device has a challenge d and a response D.

If the controller device has a challenge d, a response D, the controller's calculation means is based on each challenge d and each response D,                 

R '= G ₁ ^d ₁ × G ₂ ^d ₂ × ... × G _m ^dm × D ^v mod n, or

R '= D ^v / G ₁ ^d1 × G ₂ ^d2 × ... × G _m ^dm mod n reconstruct the commitment R' satisfying the equation, and the means for calculating and comparing the controller device is the message M and the challenge Check that d satisfies the hashing function d = h (message, R ').

If the controller has commitment R and response D:

If the controller has a commitment R and a response D, the calculating means of the controller device calculates d 'by applying a hashing function d' = h (message, R), and then calculating means of the controller device. And the comparison means that the commitment R and the challenge d 'and the response D are

R = G ₁ ^d'1 × G ₂ ^d'2 × ... × G _m ^d'm × D ^v mod n, or

R = D ^v / G ₁ ^d'1 × G ₂ ^d'2 × ... × G _m ^d'm mod n Verify that the equation is satisfied.

GQ technology aims at the dynamic authentication of entities and messages and the digital signature of messages, and is a "no knowledge transfer" technology. One entity proves that it recognizes one or more private numbers. The other entity confirms it; This entity is aware of the corresponding publish (es). The attesting entity assures the identifying entity without revealing the private number (s) so that it can use those private numbers for as long as necessary.

Each GQ pattern is based on a public modulus of large secret prime factors. The openness index v and open modulus n together form a verification key <v, n> representing &quot; v square of modulus n &quot; and one or more general formulas, i.e. all direct equations, G = Q ^v ( mod n) or vice versa with G × Q ^v = 1 (mod n). This type affects the internal operation of the identifying entity, but not inside the certifying entity; Indeed, security analysis confuses the two forms. Each general formula connects the public number G and the private number Q to form a pair of {G, Q} numbers. In summary, each GQ pattern implements one or more pairs of {G, Q} with the same key <v, n>.

Here, the conventional version of the GQ pattern called GQ1 uses an RSA digital signature pattern. Then, the verification key <v, n> is preferably an RSA public key whose non-uniform v index is a prime factor. Each GQ1 pattern generally uses a pair of numbers {G, Q}: According to the format mechanism, which is an integer part of the RSA digital signature, the publication number G is derived from the identification data. The private number Q or other inverse modulo n is the RSA signature of the identification data. The attestation entity verifies the knowledge of the RSA signature from its identifying data and the attestor does not expose the signature. Thus, the signature can be kept secret and used as many times as necessary.

The GQ1 pattern generally implements two key levels: The RSA signature private key is reserved for the organization that trusts the entity that distinguishes itself from others by means of identifying data. This pattern is called "identity based." Thus, when issuing each card, the chip card issuer uses its own RSA private key to calculate the private number Q written as the diversified private key of the card. In other cases, every time a customer on a computer network logs on, he uses his RSA private key to compute the private number Q, which is his or her private private key during that time. The attesting entity, chip card, or logged on customer knows the RSA signature of their identifying data, but not the RSA secret key just above the hierarchy of keys. However, dynamic authentication of an entity by GQ1 with 768-bit modulus at the institutional level is dynamic authentication of an entity by RSA with 512-bit modulus with three prime factors at the level of each entity. It requires almost the same workload as the difference surplus method can be used by calculating the obtained modulo to each prime factor before calculating it.

However, the hierarchy of keys between institutions and trusted entities is not mandatory. GQ1 can be used with modulus specific to the attestation entity, so that the Chinese surplus method can be used to reduce the workload of the attestation entity, but the modulus at the attestation entity level is shorter than the modulus at the institution level, eg 768. Apart from being 512 bits per bit, it does not fundamentally change the workload of the controller entity.

When an entity does not know the prime factor of its own modulus, why use the digital signature RSA pattern?

Another version of the GQ pattern, called the basic GQ2, directly uses modulus factorization problems. In this context, "directly" means "do not use RSA signatures." The purpose of GQ2 is to reduce the workload of the controlling entity as well as the workload of the attesting entity. The attestation entity demonstrates knowledge of the decomposition of its own modulus and does not expose the decomposition in this attestation. Thus, the decomposition can be kept secret and used as many times as necessary. The security of the GQ2 protocol is equivalent to the factorization of modulus.

Each attestation entity has its own modulus n. Each GQ2 pattern implements a parameter k, a larger number than 1 and a small number determined by the public index v = 2 ^k , and one or more pairs {G ₁ , Q ₁ } to {G _m , Q _m }. Each publication number G ₁ is a square of a number g _{1 which} is smaller than ₁ , and is referred to as a "base number". All attestation entities may use the same G ₁ through G _m public number (s). The factorization of the modulus n and the published number (s) with Q ₁ to Q _m is at the same level in the key hierarchy. Each set of GQ2 primary keys is defined by two conditions, both necessary and sufficient.

For each radix, none of the two equations x ² = ± g _i (mod n) is an integer module with no solution of x in the ring of n. That is, the number ± g _i is two non-quadratic residues modulo n.

For each radix, two equations, ^{v v} = ± g _i ² (mod n), with v = 2 ^k , are integer modules with solutions of x in the ring of n. The private number Q _i or its inverse modulo n is one of these solutions.

As a secondary rest (non-quadratic residues) to be the n modulo said modulus m is different from the Legendre symbol (Legendre symbol) of g _i - in the two conditions given in this manner, the number of ± g _i are two non- Include at least two prime factors that match 3 (mod 4) in this context. As a result, any modulus that does not have a prime factor or consists of one of the prime factors that match 3 (mod 4) does not establish a set of GQ2 primary keys, and supports a prime factor that matches 3 (mod 4). Randomly withdrawing half of the large prime factors proves to match 3 (mod 4) and half to 1 (mod 4). Thus, many RSA modules in use cannot establish a set of basic GQ2 keys.

In this specification, the use of GQ2 generalized key sets to overcome this limitation allows the use of GQ2 technology with any modulus, in particular with any RSA modulus. These are based on two essential and sufficient principles.

The first principle reproduces the second GQ1 basic condition.

In each radix g ₁ to g _m , the expression x ^v = g _i ² (mod n) with v = 2 ^k has the solution of x in the integer ring of modulo n.

Since each private number Q or other inverse modulo n is solved in the above equation, k-1 successive square modulo n is equal to the number q _{i which} is the square root of G _i in the integer ring of the modulo n. To convert. The number q _i is the same as the two numbers g _i or ng _i , or different from the two numbers g _i and ng _i . This is called trivial or non-simple. When the number q _i is nonsimple, n dividing q _i ² -g _i ² is q _i -g _i and q _i + g _i Do not divide both. Thus, any non-simple q _i does not expose the decomposition of the modulus n.

n = pgcd (n, q _i g _i ) × pgcd (n, q _i + g _i )

The second principle extends the first GQ2 basic condition.

Of the numbers q ₁ to q _m , at least one q _i is non-simple.

Note that if the number q + is present when the number ± g _i is the integer modulo two non-secondary remainders in the ring of n, then the number q _i is clearly non-simple. Therefore, in normal use where any modulus is available, the set of basic GQ2 keys is a complete part of the set of GQ2. That is, any configuration of large prime factors that match at least two, regardless of 3 or 1 (mod 4). On the other hand, in general use, many GQ2 key sets are not GQ2 primary key sets. Each commonly used GQ2 key set is one of two cases:

When the 2 x m numbers ± g ₁ to ± g _m are all non-secondary remainders, this is the GQ2 primary key set.

-A set of GQ2 complementary keys, not a GQ2 primary key set, when there are at least one non-secondary remainder out of the 2 x m numbers ± g ₁ to ± g _m .

By definition, the present invention relates to a set of GQ2 complete keys, which are not primary keys in normal use. Apart from the above two principles, this kind of set must satisfy the third principle.

There are at least one non-secondary remainder out of the 2 x m numbers ± g ₁ to ± g _m .

In order to recognize the problem provided in the present invention and to understand its solution, we first analyze the decomposition of modulus n exposed by the non-simple q. The concept of coefficients in the Galois field CG (p) is then understood after recalling the Chinese surplus method. Then, study the functions of the "raise to square" in CG (p) and the "take a square root" of the second order in CG (p). Finally, the applicability of the three principles will be analyzed.

Analysis of Modulus Decomposition

When modulus n decomposes into _f prime factors p ₁ to p _f , the ring of integer modulo n decomposes into f Galois fields CG (p ₁ ) to CG (p _f ). In each field, there are two square roots of the unit (eg ± 1). Therefore, there are 2 ^f square roots of the unit in the ring. Each private number Q ₁ to Q _m defines the number Δ _i = q _i / g _i (mod n), which is one of the 2 ^f square roots of the units in the ring. In other words, divide Δ _i ² − 1 by n.

When q _i is simple, i.e., Δ _i = ± 1, divide Δ _i + 1 or Δ _i − 1 by n. Thus, Δ _i does not expose any decomposition of modulus n.

When q _i is non-simple, i.e., Δ _i ≠ 1, do not divide Δ _i + 1 or Δ _i − 1 by n. Thus, Δ _i exposes the decomposition of modulus n, n = pgcd (n, Δ _i −1) × pgcd (n, Δ _i + 1). This is obtained from the value of Δ _i in each field, dividing Δ _i -1 on one side and Δ _i + 1 on the other by the prime factor (s).

Let's look at the muliplicative composition rule of the number q. Two numbers {q ₁ , q ₂ } give one composite number q ₁ × q ₂ (mod n).

When q ₁ is non-simple and q ₂ is simple, the synthetic water q ₁ × q ₂ (mod n) is non-simple, which exposes the same decomposition as q ₁ .

When q ₁ and q ₂ are non-simple and Δ ₁ = ± Δ ₂ , the synthetic water q ₁ × q ₂ (mod n) is simple, which does not expose any decomposition.

When q ₁ and q ₂ are non-simple and Δ ₁ ≠ ± Δ ₂ , the synthetic water q ₁ × q ₂ (mod n) is non-simple, which does not expose tertiary decomposition.

Three numbers {q ₁ , q ₂ , q ₃ } are four synthetic numbers {q ₁ × q ₂ , q ₁ × q ₃ , q ₂ × q ₃ , q ₁ × q ₂ × q ₃ (mod n) } Is provided. That is a total of seven numbers. In this way, when m numbers provide 2 ^m -m -1 synthetic water, the total number is 2 ^m -1.

I odd numbers g ₁ to g _i in normal use, i private numbers Q ₁ to Q _i providing _i numbers q ₁ to q _i , and consequently i numbers Δ ₁ to Δ _i, the roots of the unit. Considering the set of GQ2 keys containing, consider the other radix g _{i + 1} as the private number Q _{i + 1} giving q _{i + 1} and the resulting root Δ _{i + 1} .

A total of 2 ^{i + 1} −1 numbers consists of multiple nontrivial numbers in each of the following two cases.

Root Δ _{i + 1} is simple and at least one of roots Δ ₁ to Δ _i is non-simple.

Root Δ _{i + 1} is non-simple and appears out of 2 × i roots ± Δ ₁ to ± Δ _i .

The root Δ _{i + 1} is non-simple, and when it does not appear among 2 x i roots ± ₁ to ± Δ _i , each synthetic number in which q _{i + 1} appears is non-simple.

As a result, when there is at least one non-simple form out of the m numbers q ₁ to q _i , more than half of the total 2 ^m −1 numbers are non simple forms.

By definition, l <f non-simple {q ₁ , q ₂ , ..., q _l } are independent of modulus n when each of 2 ^l -1 -1 corresponding synthetic numbers is non-simple. That is, the total number of 2 ^l -1 numbers can be said to be non-simple. Subsequently, each 2 ^l -1 number each exposes a different decomposition of modulus n.

When the f prime factors are distinguished, there are 2 ^f-1 −1 decompositions of the modulus n. Followed by, f-1 if the number of q is independently, f-1 can be independent and 2 ^f-1 -f of the corresponding synthetic Sur including total 2 ^f-1 -1 of the number and, 2 ^f-1 42-1 decomposition of There is a one-to-one correspondence.

Difference surplus-two numbers a and b primed between 0 <a < _b , with two numbers X _a from 0 to a-1 and X _b from 0 to b-1 To be. It is important to define the unique number from 0 to a × b-1 so that X _a = X (mod a) and X _b = X (mod b). The number x = {b (mod a)} ⁻¹ (mod a) is the parameter of the difference surplus. Below is the basic operation of the difference surplus.

x = X _b (mod a)

y = X _a -x; If y is negative, y is replaced by y + a.

z = a × y (mod a)

x = z × b + x _b

In summary, we write x = difference surplus (X _a , X _b ).

When f prime factors are assigned to the ascending order, from minimum p ₁ to maximum p _f , the difference surplus parameter is as follows (one less than the prime factor, ie f-1).

The first parameter is x = {p ₂ (mod p ₁ )} ^-1 (mod p ₁ ).

The second parameter is β = {p ₁ × p ₂ (mod p ₃ )} ⁻¹ (mod p ₃ ).

The i-th parameter is lambda = {p ₁ × p ₂ × ... × p _i-1 (mod p _i )} ⁻¹ (mod p _i ).

- etc.

In the f-1 basic operations, the number X is established from 0 to n-1 from any set of f elements from X ₁ to X _f where X _j is 0 to p _j-1 .

The first result (mod p ₁ × p ₂ ) with the first parameter

Then, the second result (mod n = p ₁ × p ₂ × p ₃ ) with the second parameter

With final parameters up to the final result (mod p ₁ × p ₂ × ... × p _f ).

In summary, given the prime factors p ₁ to p _f , each element of the ring of n modulo has two equivalent representations.

f number x ₁ to x _f , one component per prime factor: X _f = X (mod p _f ),

-Numbers from 0 to n-1 x, X = differential surplus (X ₁ , X ₂ , ..., X _f )

In CG (p) there are rank -uneven prime factors p and a number a less than p. Ie 0 <a <p. If defined, the coefficient of a to p is {x ₁ = a; then, for i≥1, x _{i + 1} = a ^p xx _i = (mod p)}. By Fermat theory, the coefficient of number a to the prime factor p is a divisor of p-1 or p-1.

For example, when (p-1) / 2 is an odd prime factor p ', the Galois field CG (p) contains a number having a coefficient of one. This is 1. The number 2 is -1. If the coefficient is p ', it is p'-1 number, and if the coefficient is 2xp' = p-1, it is p'-1 number. In CG (p), any number with coefficient p-1 is a "generator". This name implies that the stream {X} term forms a permutation of all non zero elements of CG (p) for successive powers of the generators of CG (p), i. Due to the fact.

There is a constructor y of CG (p), and evaluate the coefficient of the number y (mod p) as a function of i and p-1. When i is small with p-1, it is p-1. When dividing p-1 by i, it is (p-1) / i. In all cases, this is (p-1) / pgcd (p-1, i).

By definition, Euler function φ (n) is less than n and is the number of prime numbers. In CG (p), there is a φ (p-1) constructor.                 

By the illustrated description, the coefficients can better understand the basics of RSA. Modulus n is a product of _f prime factors p ₁ to p _f ( _f ≧ 2). For each prime factor p _j of p ₁ to p _f , the publication index e must be prime with p _j −1. The key <e, p _j > then relates to a coefficient that is an element of CG (p _f ). This permutates the elements of CG (p _j ). There is a number d _j (usually the smallest possible number) such that p _j −1 is e × d _j . The key <d _j , p _j > inverts the permutation of CG (p _j ) elements. One of each of these f permutations, namely CG (p ₁ ) to CG (p _i ), is represented by an RSA permutation arranged by the public key <e, n> in the ring to the integer module. There is a number d (usually the smallest possible number) such that ppcm (p ₁ -1, p ₂ -1, ..., p _j -1) becomes d xe -1. For each prime factor p _j of p ₁ to p _f , we have d _j = d (mod p _f −1). The RSA permutation arranged by the public key <e, n> is inverted by the private key <d, n>.

Square in CG (p) -Define the number t so that p-1 can be divided by 2 ^t rather than by 2 ^{t + 1} . Each of the large prime factors is represented by one category alone, that is, t = 1, t = 2, t = 3, t = 4, and the like. Considering a sufficiently large number of consecutive prime factors, one of the two appears in the first category where p matches 3 (mod 4), and one of the four has a second category where p matches 5 (mod 8). And one of the eight appears in the third category where p matches 9 (mod 16). In addition, one of the 16 appears in this way, such that p appears in a fourth category that matches 17 (mod 32). The average, one of the two 2 ^t t is shown in the category that matches the p ^{2 t +1 (mod 2 t +} 1).

Since the numbers x and p-x have the same square in CG (p), the keys <2, p> permutate CG (p). The function "square operation" in CG (p) is represented by an oriented graph in which each non-zero element of the field is placed. Analyze the structure of the graph in branches and circles according to the parity of the coefficients of each element.

-Zero element is fixed. It is 0 and the coefficient is not defined for zero element. The zero element is not connected to other elements and is isolated.

The unit element is fixed. This is 1, only an element with one coefficient. The root of the unit in the coefficient CG (p) is in the branch connecting 1. y is the non-quadratic residue of CG (p). The key <(p-1) / 2 ^t , p> converts y to a 2 ^t-1 primitive root of -1 represented by b. In fact, we have y ^{(p-1) / 2} = -1 (mod p). As a result, in CG (p), the power of b for an exponent of 1 to 2 ^t-1 is 2 ^t-1 -1 roots of the unit different from ¹ . These constitute a branch associated with one.

The square of any element of an even coefficient is another element with coefficients divided by two. As a result, each element of each even coefficient is placed in a branch. Each branch contains coefficients that are divided into two but not divided into four. Then, if t ≧ 2, it includes two coefficients that can be divided into four but not divided into eight. In addition, if t≥3, it contains four coefficients that can be divided into eight but not divided into sixteen, and if t≥4, it includes eight coefficients that can be divided into eight but not divided by sixteen. Is done. All branches are similar to branches associated with one. 2 ^t-1 leaves of each branch are non-secondary runoff. Each branch contains 2 ^t −1 elements and is connected to an odd rank. There are (p-1) / 2 ^t branches, all of which have the same length t.

The square of any element that is an odd coefficient different from the unit element is another element with the same coefficient. The key <2, p> permutes all (p-1) / 2 ^t elements of odd coefficients. The permutation decomposes into a permutation cycle. The number of cycles depends on the factorization of (p-1) / 2 ^t . For each divisor of (p-1) / 2 ^t , there is a cycle including the φ (p ') element of the coefficient p'. By definition, remember that Euler's function φ (p ') is a number less than p' and less than p '. For example, when p '= (p-1) / ^2t is small, the number of p'-1 of the coefficient p' is a large permutation cycle.

1a to 1d are graph parts of p corresponding to 3 (mod 4), 5 (mod 8), 9 (mod 16) and 17 (mod 32), respectively.

The leaf of the branch is indicated by a white circle. This is non-secondary residues.

Nodes in branches are shown as gray circles. This is the secondary of even coefficients.

The nodes of the cycle are marked with black circles. This is the secondary of even coefficients.                 

Square Root in CG (p)-Knowing that a is the second run of CG (p), the solution to the equation x ² = a (mod p), ie the "square root operation" in CG (p) Let's find out. Of course there are several ways to achieve the same result. See Henry Cohen, "a Course in Computation Algebraic Number Theory (vol. 138 of series Graduate Texts in Mathematics, 138 (GTM 138), pages 31-36, published by Springer, 1993, Berlin).

The number s = (p-1 + 2 ^t ) / 2 ^{t + l} gives the keys <s, p> worth

When p matches 3 (mod 4), <p + 1) / 4, p>,

When p matches 5 (mod 8), <p + 3) / 8, p>,

<p + 7) / 32, p> when p matches 9 (mod 16),

<p + 15) / 32, p> when p matches 17 (mod 32), etc.

The key <s, p> converts any element in the cycle to the preceding element of the cycle. When a is an even coefficient, it is a solution of odd coefficients. This is called w here. Indeed, in CG (p), w ² / a is worth (2 × (p-1 + 2 ^t ) / 2 ^{t + 1} ) -1 = (p-1) / 2 ^t squared a. The other solution is an even coefficient. This is pw.

In a general manner, the key <s, p> converts any secondary flow a into a first solution approximation called r. Since a is the second flow, the key <2 ^t-1 , p> reliably switches r ² / a to 1. To approximate the square root of a, r ² / a is squared by 2 ^t-2 (mod p) to obtain +1 or -1. If the result is +1, the new approximation remains r. If the result is -1, the new approximation is b x r (mod p). Where b represents any 2 ^th order primitive root of 1 in field CG (p). It is also possible to approximate by using the keys <2 ^t-3 , p> and multiply b ² (mod p) as needed. There are various ways to do this.

The algorithm below solves the equation: We use the numbers a, b, p, r and t previously defined, and two variables c and w. C denotes successive correction and w denotes successive approximation. In the beginning of the algorithm, c = b and w = r. At the end of the operation, the two solutions are w and p-w.

For i between t-2 and 1, the following sequence is repeated.

-Apply key <2 ^t , p> to number w ³ / a (mod p) to get +1 or -1

If -1 is obtained, replace w with w xc (mod p).

replacing c with c ² (mod p).

Applicability of the Principle -By definition, the parameter k, radix g and prime factor p are compatible when the expression x ^v = g ² (mod p) with an index v of 2 ^k cannot be solved with x in the ring of field CG (p). It is called (compatible). The numbers k and g are small but larger than one. The number p is a large prime number.

When t = 1, ie p = 3 (mod 4), the equation has two solutions.

When t = 2, i.e., when p = 5 (mod 8), the equation has four solutions, if (g│p) = + 1, depending on the Rejangdre symbol of q associated with p If) =-1, the equation has no solution.

When t> 2, i.e. when p = 1 (mod 8), ^u divides the coefficient of the open number G = g ² related to p by 2 ^u and does not divide it by 2 ^u-1 . As a result, u is equal to one of the numbers 0 to t-1. If u> 0 and k + u> t, then the equation has no solution, and if k + u ≦ t there are 2 ^k solutions. Further, if u = 0 and k> t, the equation has 2 ^t solutions.

Thus, G has two types of compatibility depending on whether or not it is properly positioned in the cycle or in the branch.

When G is in the cycle, i.e., u = 0 regardless of the value of k, the solution of the odd coefficients in the cycle and the even number interspersed with α = min (k, t), the continuous branch connected to the cycle There are solutions of the coefficients (ie, all 2 ^α solutions). 2A shows the case where k ≧ t = 3. That is, the case where the prime factor corresponding to 9 (mod 16) which imposed u = 0 is shown.

When G is in the proper position of the branch, i.e. when u> 0 and u + k ≦ t, there are 2 ^k solutions, which are in the branch and are all even coefficients. Fig. 2B shows this case.

Given a parameter k, there are two types of prime factors from there, depending on whether the value of t is less than or equal to k.                 

For any prime factor p _j that satisfies t <k, each G _i must be in cycle, and there is no solution in the branch connected to G _i . Define a number Δ _ij which becomes +1 or -1 depending on whether g _i or-g _i is in the cycle. There is no selection for some of the _m numbers Δ _{1, j} to Δ _{m, j} . 3A shows the case where t <k. G _i is in a cycle with a prime factor p _j equal to 9 (mod 16). That is, u = 0 and t = 3 where k> 3.

For any prime factor p _j that satisfies t≥k, each G _i must be in a cycle that satisfies u + k ≤ t, i.e. u = 0, or in the proper position for a branch of 1 ≤ u ≤tk . Q _ij that is connected to the g _i in the cycle defines the number Δ _ij which, depending on whether the connection with -g _i, +1 or -1. for each of the m numbers Δ _{1, j} to Δm _{, j} . Each of Δ _{i, j} can be individually varied between one value and the other. 3B shows the case where t ≧ k. G _i is in a cycle with a prime factor p _j equal to 17 (mod 32). That is, u = 1 and k = 3, t = 4.

Each set of _f components {Δ _{i, 1} , Δ _{i, 2} , ..., Δ _{i, f} } is the square root of the unit in CG (p _f ). This root is either simple or non-simple, depending on whether the f components are equal. The set of f-components is then called a constant or variable, indicating the fact that the number q _i is simple or non-simple. As a result, when q _i is simple, the set of f components {Δ _{i, 1} , Δ _{i, 2} , ..., Δ _{i, f} } summarizes the decomposition of the module. It is then possible to test this principle before calculating the secret component Q _{i, j} .

When the publication number G _i is present in the cycle for the prime factor p _j , the number Δ _{i, j} becomes +1 or −1 depending on whether g _i or-g _i is in the cycle. When p _j = 3 (mod 4), this is the Rejangdre symbol: Δ _{i, j} = (g _i │ p _j ).

When the public number G _i is present at a suitable position in the branch to the prime factor p _j , the value to be given to Δ _{i, j} may be determined before calculating the secret component Q _{i, j} .

Generation of Key Sets- Given a parameter k, there are two ways.

In one scheme, the generator requires f prime factors to determine m bases. First prime factors: 2,3,5,7 and the like are examined to evaluate compatibility with each of the _f large prime factors p ₁ to p _f . Although g = 2 is incompatible with p = 5 (mod 8), 2 can be a base composition. In fact, when the two numbers are in similar positions of the branch, the product is closer to the cycle, as the square approaches the cycle. In this way the radix can be obtained by including numbers that are not individually suitable.

Or, in another way, the generator may use m radix and bit sizes (e.g., 512,768,1024,1536,2048) and number of higher order bits greater than 1 to determine f≥2 prime factors. For example, modulus characteristics such as 1, 8, 16, 24, 32 are required. When the radix is represented by G ₁ , G ₂ ,..., G _m , the radix is generally represented by a number in a first prime factor: ₂ , ₃ , ₅ , ₇ , ₁₁ , or the like, or a combination of the first prime factors. to be. Otherwise, if not specified, the radix is m first prime factors: G ₁ = 2, G ₂ = 3, G ₃ = 5, G ₄ = 7 and the like. Note that p = 5 (mod 8) is not compatible with g = 2. The modulus n may be a product of a neighboring size, i.e., f prime factors that are sizes allocated to f modulus divided by f.

First Principle -Each prime factor p of the parameters k, p ₁ to p _f and each base g of g ₁ to g _m should be compatible. Define h to divide the coefficient of g associated with p by 2 ^h . In contrast, the coefficient cannot be divided by 2 ^{h + 1} . In order to calculate this number h, the procedure below uses the genre symbol (g | p) and the second ^t order primitive root of the unit at number b, ie CG (p).

If t = 1 (g | p) = +1, respond with "h = 0".

If t> 1 (g | p) = +1, the key <p-1 + 2 ^t ) / 2 ^{t + 1} , p> is applied to G to obtain a result of w.

If w = + g, reply with "h = 0".

If w = p-g, respond with "h = 1".

Otherwise, substitute c for b and for i of t-1 to 2.                 

Apply the key <2 ⁱ , p> to w / g (mod p) to get ± 1.

If -1, substitute h for i and replace w with w × c (mod p)

replace c with c ² (mod p)

-if (g | p) = -1, reply with "h = t".

Recall that when k> u> t, u> 0, k, g and p are incompatible. They are compatible irrespective of the value of k when h = 0 or 1, and are compatible even when k> 1 in k + h ≦ t + 1.

Second Principle -The three procedures below correspond to different implementations of the second principle. In some implementations, the second principle can be enhanced to the extent that each number of q ₁ to q _m is non-simple. The role of the rider is then balanced. Whether the second principle is balanced or not affects the aspect demonstrating the security of the pattern. Finally, when there are f> 2 different prime factors out of _m numbers {q ₁ to q _m }, it is possible to request at least one subunit of f-1 independent numbers.

The three procedures use m x f numbers δ _{i, j} , defined as follows.

p _j is t <k, where δ _{i, j} = Δ _{i, j} (i runs from 1 to m). That is, if h _{i, j} = 0, it is +1, and if h _{i, j} = 1, it is -1.

p _j is δ _{i, j} = 0 (i goes from 1 to m) when t≥k, which shows that we can choose Δ _{1, j} to Δ _{m, j} as a function of the second principle .

The first procedure checks whether at least one of the sets {δ _{i, 1} to δ _{i, f} } is variable or zero, that is, the number of at least one of the numbers q ₁ to q _m can be chosen as non-simple or non-simple. .

i goes from 1 to m, j goes from 1 to f,

If δ _{i, j} = 0 or ≠ δ _{i, 1} , respond with "success."

Respond "failure"

The second procedure checks whether each of the sets {δ _{i, 1} to δ _{i, f} } is variable or zero, ie, the number of at least one of the numbers q ₁ to q _m can be chosen as non-simple or non-simple.

i runs from 1 to m,

j goes from 1 to f,

If δ _{i, j} = 0 or ≠ δ _{i, 1} , then proceed to the next i value.

-Respond with "failure"

-Respond with "success"

The third procedure involves at least one set, for each pair of prime factors p _j1 and p _j2 , where ₁ ≦ j ₁ ≦ j ₂ ≦ f, where δ _{i, j1} is zero or different from δ _{i, j2} {δ _{i, 1} , Check if δ _{i, 2} , ..., δ _{i, f} } is present. Obviously it fails when m is less than f-1. On success, there is at least one set of f-1 independent numbers related to f prime factors among the _m numbers q ₁ to q _m .

j ₁ goes from 1 to f-1, j ₂ goes from J ₁ +1 to f,

i goes from 1 to m,

If δ _{i, j} = 0 or ≠ δ _{i, 1} , proceed to the next value of j ₁ and j ₂ .

-Respond with "failure"

-Respond with "success"

If the procedure fails, the generator of the GQ2 key set performs one of two ways:

Changing one of the m bases while maintaining the f prime factors.

Changing one of the f prime factors while maintaining m bases.

Principle 3 -The procedure below is generated or a generic set of generated GQ2 keys:

Whether the GQ2 primary key set, ie 2 x m numbers ± g ₁ to ± g _m, are all non-secondary flows,

Or, it is determined whether at least one of the GQ2 completeness key sets, i.e., 2 x m numbers ± g ₁ to ± g _m , is a secondary flow.

The procedure uses two Legendre symbol is (g _i │p _j) and _(i │p -g _j) when i is conducted until between 1 m j is conducted from 1 to f.

i runs from 1 to m,

j goes from 1 to f,

If (g _i │ p _j ) = -1, it proceeds to the next i value.

Respond with a "GQ2 complete key set".

j goes from 1 to f,

-(-g _i │ p _j ) = -1, proceeds to the next i value.

Respond with a "GQ2 complete key set".

Reply with "GQ2 primary key set".

Secret component -direct form: In the equation of x ^v = g _i ² (mod p _j ), the following operation establishes all possible values of secret component Q _{i, j} . The two most simple and most common cases (ie, when t = 1 and t = 2) are described followed by the most complex case (ie, when t> 2).

For t = 1, i.e., p _j = 3 (mod 4), the key <(p _j +1) / 4, p _j > is the square quadratic root of any quadratic run in CG (p _j ) ). The key to derive the number s _j = ((p _j +1) / 4) ^k (mod (p _j -1) / 2), converting G ₁ to w = G ₁ ^sj (mod p _j ) <s _j , p _j > Q _{i, j} is equivalent to w or p _j -w.

For t = 2, i.e. p _j = 5 (mod 8), the key <(p _j +3) / 8, p _j > gives the square quadratic root of the odd coefficient of any element in CG (p _j ) do. The key to derive the number s _j = ((p _j +1) / 8) ^k (mod (p _j -1) / 4), converting G _i to w = G _i ^sj (mod p _j ) <s _j , p _j > Since 2 is a non-second-order flow in CG (p _j ), we must examine whether z = 2 ^{(pj-1) / 4} (mod p _j ) is the square root of -1. Q _{i, j} is equivalent to w or p _j -w, or is equivalent to w = w x z (mod p _j ) or p _j -w '.

For p _j = 2 ^t +1 (mod 2 ^{t + 1} ) with t> 2, the key <(p _j -1 + 2 ^t ) / 2 ^{t + 1} , p _j > is random in CG (p _j ) Gives the square root of the odd coefficient of the element of. The compatibility test between k, g and p gives the h value followed by the u value.

The number s _j = ((p _j −1 + 2 ^t ) / 2 ^{t + 1} ) ^k (mod (p _j −1) when G _i is in a cycle (u = 0 regardless of k value) / 2 ^t ). Key <s _j, p _j> is converted to G ₁ ^sj (mod p _j) of the odd-numbered coefficient G _i. There is a solution of even coefficients distributed over successive branches min (k, t) connected to the cycle, also called a branch. Q _{i, j} is equivalent to the product of w and any root of the 2 ^? Order roots of the unit in CG (p _j ).

When G _i is in the proper position of the branch (u> 0, u + k ≦ t), all solutions are in the same branch as G _i, and the branch is cycled by the 2 ^u -order square of the number G _i . Is connected to. The number s _j = ((p _j −1 + 2 ^t ) / 2 ^{t + 1} ) ^{k + u} (mod (p _j −1) / 2 ^t ) is established. The keys <s _j , p _j > convert the 2 ^u -order squares of G _i to the number of w, which is an odd coefficient. Includes 2 ^{α-dimensional} product of all Q _{i, j} of sigeun and w in the CG (p _j).

- p and t _j is ≥k, b _j be a CG (p _j) of 2 units at ^t - when primary source of these days, 2 ^tu of b _j in CG (p _j) - squared difference is present. This is the 2 ^k -order primitive root of the unit. The value of the number Δ _{i, j} can be swung by multiplying Q _{i, j} by the 2 ^k -order primitive roots of the unit.

Inverse: In the equation 1 = x ^v xg _i ² (mod p _j ), replace the number s _j with ((p _j -1) / 2 ^t ) -s _j in the key <s _j , p _j > It is enough to replace with. This is to switch the value of Q _{i, j} in CG (p _j ).

Example of a keyset containing two prime factors that match 5 (mod 8)

Hereinafter, the first few Regendre symbols.

(2 | p ₁ ) = -1; (3 | p ₁ ) = -1; (5 | p ₁ ) = -1; (7 | p ₁ ) = -1; (11 | p ₁ ) = +1;

(13 | p ₁ ) = -1; (17 | p1) = +1;

In CG (p2) the coefficients are odd for -5, -11 and 17.

(2 | p ₂ ) = -1; (3 | p ₂ ) = +1; (5 | p ₂ ) = +1; (7 | p ₂ ) = +1; (11 | p ₂ ) = +1;

(13 | p ₂ ) = -1; (17 | p ₂ ) = -1;

In CG (p ₂ ) the coefficient is odd for 3, -5, 7 and 11.

The carmichael function is λ (n) = scm ((p ₁ -1) / 4, (p ₂ -1) / 4).

When k = 9, σ = λ (n)-((1 + λ (n)) / 2) ⁹ (mod λ (n)) as the secret exponent for using a general function of the inverse function form.

2, 3, 7, 13 and 17 are not suitable as bases.

The key <σ, n> converts g ₁ = 5 into an inseparable secret value Q ₁ . That is, 5 is repeated in both regions.

The key <σ, n> converts g ₂ = 11 into a secret value Q ₂ that is decomposed. In other words, 11 is not in the same position in both areas.

The key <σ, n> converts g ₃ = 21 = 3 × 7 into a secret value Q ₃ which is decomposed.

The key <σ, n> converts g ₄ = 26 = 2 × 13 into a secret value Q ₄ which is decomposed.

The secret key can still be represented by two prime factors, the parameters of the Chinese remainder and the eight secret elements.

Polymorphism of GQ2 Secret Keys-Various possible forms of GQ2 secret keys prove to be equivalent: equivalent to the knowledge of factorization of modulus n, which is a true GQ2 secret key. This type of GQ2 secret key strives for computation in the attestation entity, not in the controlling entity. Below are three possible main forms of GQ2 secret keys. 1) The standard form of the GQ secret key consists of the storage means of the m secret values Q _i and the public check key <v, n> for the GQ2 pattern. This form is comparable to the following two forms. 2) The optimal form for the work load consists of storing parameters k, f prime factors p _j , m × f secret elements Q _{i, j} and f-1 parameters of the Chinese remainder. 3) The optimal form associated with the secret key size is to store the parameters k, m radix g _i and f prime factors p _j , and then set m secret values Q _i and modulus n to return to the first form or the second. Each use can be started by setting the m × f secret elements Q _{i, j} and f−1 parameters of the Chinese remainders to return to the form.

Since the dynamic authentication mechanism or digital signature mechanism is the same as the decomposition knowledge of the modulus, GQ2 patterns cannot be used to simply distinguish two entities using the same modulus. In general, each entity that has itself has its own GQ2 modulus. However, however, two can specify GQ2 modulus with four prime factors that one entity knows and the other two know.

Dynamic authentication -The dynamic authentication mechanism is designed to verify the authenticity of another entity known as a controller to the entity known as the controller, and the authenticity of the message M associated with it. Thus, the controller can confirm that it is exactly the prover, in some cases only the prover, and can verify that the prover is speaking the same message M correctly. The related message M is optional. This means it can be blank.

The dynamic authentication mechanism consists of a series of four behavior processes consisting of commitment behavior, challenge behavior, response behavior and checking behavior. The prover performs the actions of commitments and responses. The controller performs challenge and control actions.

Within the prover, it is possible to separate the witness in such a way as to separate the prover's most sensitive parameters and functions, namely the results of commitment and response . The witness may, upon processing, parameter k and a secret key GQ2, i.e., one of the three forms described above (f primes and m bases, m × f secrets and f primes and difference surplus f). -Factor of modulus n according to one parameter, one of m secret values and one of modulus n).

The witness corresponds to a partial embodiment (e.g., a chip card connected to a PC forming a full proof or a special security program installed in a PC or a special security program installed in a chip card). The witnesses thus separated are similar to the witnesses defined below within the signing party. In each implementation of the mechanism, the witness creates one or more commitments R, followed by multiple responses D and multiple challenges d. Each set {R, d, D} is a GQ2 triplet .

Apart from the configuration of the witness, the prover also has a hashing function and message M, if necessary.

The controller has modulus n at processing, for example from a directory of the public key or from a register of the public key, and has the same hashing function and message M 'if necessary. The GQ2 disclosure parameters, ie the numbers k, m and g ₁ to g _m, are given to the controller by the prover. The controller can recover commitment R 'from any challenge d and any response D. The parameters k and m inform the controller. On the contrary, if any instruction fails, m radix from g ₁ to g _m are m first prime numbers. Each challenge d must have m initial elementary challenges represented by d ₁ to d _m , one per nose. The initial challenge from d ₁ to d _m may have a value between 0 and 2 ^{λ −1} −1 (the value of v−1 on v / 2 is not used). Typically, each challenge is encoded by m × k−1 bits (not m × k). For example, when k = 5 and m = 4, and when the radix 5, 11, 21 and 26, each challenge has 16 bits transmitted in 4 quarts. When the (k-1) x m challenges are possible, the (k-1) x m value determines the security provided by each GQ2 triplet. The so-called impostor, not knowing the factorization of modulus n, has exactly one chance of success at 2 ^{(k-1) .m} . When (k-1) x m is between 15 and 20, one triplet is sufficient to reasonably provide for dynamic authentication. To achieve any level of security, triplets can be provided in parallel. It is also possible to provide continuously, ie to repeat the execution of the mechanism.

1) Commitment behavior consists of the following operations:

When the witness does not use the Chinese remainders, the witness has m secret values and modulus n from parameters k, Q ₁ to Q _m in processing. The witness issues one or more random value r (0 < r < n) randomly and privately. Subsequently, each random value r is converted into a commitment R by k continuous square (mod n) operations.

R = r ^v (mod n)

The following is an example with a conventional key set having no Chinese remainders.

When the witness uses Chinese remainders, in processing the witness has parameters k, f primes from p ₁ to p _f , f-1 parameters of Chinese remainders and m × f secret elements Q _{i, j} . The witness randomly and privately issues one or more collections of f random values, each collection having one random value r _i for each prime factor p _i (0 <r _i <p _i ). Subsequently, by random operation k squared (mod p _i ), each random value r _i is converted into a commitment element R _i .

R _i = r _i ^v (mod p _i )

For each collection of f commitment elements, the witness establishes a commitment in accordance with the description of the difference surplus. There are as many commitments as there are collections of random values.

R = Difference surplus (R ₁ , R ₂ , ..., R _f )

Below is an example with a conventional key set with Chinese remainders.

In both cases, the prover sends the controller a hashing code H that can be obtained by hashing all or some of each commitment R, or each commitment R and one message M.

2) Challenge behavior is the irregular issue of one or more challenges d, each consisting of m initial challenges d ₁ , d ₂ , ...., d _m . Each initial challenge d _i has one of values between 0 and v / 2-1.

d = d ₁ , d ₂ , ..., d _m

The following is an example for a first set of keys with k = 5 and m = 4.

d ₁ = 1010 = 11 = 'B'; d ₂ = 0011 = 3; d ₃ = 0110 = 6; d ₄ = 1001 = 9,

d = d ₁ ∥ d ₂ ∥ d ₃ ∥ d ₄ = 10110011 01101001 = B3 69

The controller sends each challenge d to the prover.

3) Response action has the following operation.

When the witness does not use Chinese remainders, the witness has parameters k, m secret values and modulus n from Q ₁ to Q _m in processing. The witness calculates one or more responses D using each random value r of the behavior of the commitment and the secret value according to the initial challenge.

D = r _i × Q _i ^d1 × Q ₂ ^d2 × ... × Q _m ^dm (mod n)

The following is a series of examples without having the Chinese remainders.

When the witness uses the Chinese remainders, the witness has the parameters k, f prime factors from p ₁ to p _f and m × f secret elements Q _ij . The witness calculates one or more collections of f response elements using each collection of random values of commitment behavior, each collection of response elements consisting of one element per prime factor.

D = r × Q ₁ ^d1 × Q ₂ ^d2 × ... × Q _m ^dm (mod n)

For each collection of response elements, the witness establishes a response in accordance with the Chinese rest technique. There are as many responses as there are challenges.

D = Chinese remainders (D ₁ , D ₂ , ..., D _f )

The following is a series of examples with Chinese residues.

D1 = r _i × Q _1,1 ^d1 × Q _2,1 ^d2 × Q _3,1 ^d3 × Q _4,1 ^d4 (mod p1)

In both cases, the prover sends each response D to the controller.

4) The inspection act verifies that each triplet {R, d, D} verifies the following form of expression for non-zero values, or

In addition, it will reset each commitment. None should be zero.

If necessary, the controller then hashes each recommitted commitment R 'and message M' respectively to calculate the hashing code H '. Thus, the dynamic authentication is successful when the controller retrieves at the end of the first commitment action, i.e., all or part of each commitment R, or the hashing code H.

For example, a series of initial operations convert response D to commitment R '. The operation allows k powers (mod n) to be divided into radix k-1 divisions or multiplications (mod n). If the i-th square and the i-th division or a multiplication is carried out between the i + 1-th square, the i-th bit of the initial challenge d ₁ is indicated whether it is necessary to use a g _1, and the initial challenge d ₂ The i th bit indicates whether it is necessary to use g ₂ , and in this way up to whether the i th bit of the initial challenge d _m needs to use g _m .

The following is a final example in which no Chinese remainder is provided.

Modulo n squares:

Multiply modulo n by 5 × 26 = 130, ie '82':

Modulo n squares:

Multiply modulo n by 21, or '15':

Modulo n squares:

Multiply modulo n by 5 × 11 × 21 = 1155, or '483':

Modulo n squares:

Multiply modulo n by 5 × 11 × 26 = 1430, or '596':

Modulo n squares:

The commitment R was found. The authentication was successful.                 

The following is an example of the case having the Chinese remainder.

Modulo n squares:

Multiply modulo n by 5 × 26 = 130, ie '82':

Modulo n squares:

Multiply modulo n by 21, or '15':

Modulo n squares:

Multiply modulo n by 5 × 11 × 21 = 1155, or '483':

Modulo n squares:

Multiply modulo n by 5 × 11 × 26 = 1430, or '596':

Modulo n squares:

The commitment r was found. The authentication was successful.

Digital signature

According to the digital signature mechanism, an entity called a signatory creates a signed message, and an entity called a controller can verify the signed message. The message M is any binary sequence. It may be empty. The message M is signed by attaching a signature appendix. The signature appendix consists of one or more commitments or challenges, as well as corresponding responses.

The controller has modulus n in processing, for example from a directory of the public key or from a register of the public key. The controller also has the same hashing function. The GQ2 public parameters, ie the numbers k, m and g ₁ to g _m, are given to the controller by the prover, for example by entering in the signature appendix.

The parameters k and m provide information to the controller. First, the initial challenge from d ₁ to d _{m is} between 0 and 2 ^k-1-1 (the value of v-1 at v / 2 is not used). Second, each challenge d must consist of m initial challenges, represented by d ₁ to d _m . That is, the number is equal to the number of radix. On the contrary, if the indication fails, g ₁ to g _m The m bases are the m first prime numbers. If (k−1) × m is equal to 15 to 20, it is possible to sign with four triplets GQ2 generated in parallel. If (k-1) x m is equal to or more than 60, it is possible to sign with one triplet GQ2. For example, if k = 9 and m = 8, one triplet GQ2 is sufficient. Each challenge is 8 bytes and the cardinality is 2, 3, 5, 7, 11, 13, 17 and 19.

The signature arithmetic process is a series of three acts, including commitment acts, challenge acts, and response acts. Each action produces one or more GQ2 triplets, each of which consists of a commitment r (≠ 0) and m initial challenges represented by d ₁ , d ₂ , ..., d _m 0).

The signer has a factoring of modulus n according to the type of hashing function, parameter k and GQ2 secret key, ie one of the three forms described herein above, upon processing. In the scope of the signer, it is possible to separate the commitment and response witnesses to separate the prover and the most sensitive functions and parameters. To calculate the commitment and response, the witness has a factor k and a GQ2 secret key, i.e., one of the three forms described above, with a factorization of modulus n according to the form. The witnesses thus separated are similar to the witnesses defined in the attestor. This corresponds to a particular embodiment, for example a particular security program installed within a chip card or a chip card connected to a PC or a PC connected to a PC forming an entire signer.

1) Commitment behavior consists of the following operations.

The witness issues one or more random values r (0 <r <n) randomly and privately when it has m secret values and modulus n from Q ₁ to Q _m in processing. Subsequently, each random value r is converted into a commitment R by k continuous square (mod n) operations.

R = r ^v (mod n)

The witness may, upon processing, issue one or more collections of randomly and randomly f random values when having f prime factors from p ₁ to p _f and m × f secret elements Q _ij . Has one random value r _i for each prime factor p _i (0 <r _i <p _i ). Then, by random operation k squared (mod p _i ), each random value r _i is converted into a commitment element R _i .

R _i = r _i ^v (mod p _i )

For each collection of f commitment elements, the witness establishes a commitment in accordance with the description of the difference surplus. There are as many commitments as there are collections of random values.

r = Difference surplus (R ₁ , R ₂ , ...., R _f )

2) The challenge action is that the signer hashes all commitment R and M signed messages to obtain a hashing code that forms one or more challenges, each of which consists of m initial challenges. Each initial challenge has one of the values between 0 and v / 2-1. For example, k = 9 and m = 8. Each challenge consists of 8 bytes. There is the same number of challenges as commitments.

D = d ₁ , d ₂ , ..., d _m extracted from the resulting hash (M, R)

3) Response action consists of the following operations.

When the witness has m secret values Q ₁ to Q _m and modulus n, the witness calculates one or more responses D using each random value r of the commitment and secret value behavior according to the initial challenge.

X = Q ₁ ^d1 × Q ₂ ^d2 × ... × Q _m ^dm (mod n)

    D = r × X (mod n)

The witness may, at runtime, have _{one or} more primes from p ₁ to p _f and m × f secret elements Q _ij , using each collection of random values of commitment behavior, using one or more collections of f response elements ( collection), and each collection of response elements consists of one element per prime factor.

X _i = Q _{1, i} ^d1 × Q _{2, i} ^d2 × ... × Q _{m, i} ^dm (mod p _i )

D _i = r _i X _i (mod p _i )

In each collection of response elements, the witness establishes a commitment in accordance with the difference surplus technique. There is the same number of responses as the challenge.

D = difference surplus (D ₁ , D ₂ , ..., D _f )

The signer signs the message M when adding a signature addendum containing :

Each GQ2 triplet, ie each commitment R, each challenge d, and each response D

Or, each commitment R and its corresponding response D,

Or, for each challenge d and the corresponding response D, respectively.

The implementation of the verification operation depends on the content of the signature appendix. There are three cases for this dependency.

If the appendix consists of more than one triplet , the checking operation has two independent procedures that are independent of chronology. Only when the following two conditions are fulfilled, the controller will accept the signed message.

First, each triplet must be consistent (an appropriate relationship of the following types must be authenticated) and acceptable (compare by nonzero).

For example, the response D is switched in a series of initial operations. That is, k squared (mod n) is divided into bases of kl times or divisions (mod n). For the i th multiplication or division performed between the i th square and the i + 1 th square, the i th bit of the initial challenge d ₁ indicates whether it is necessary to use g ₁ . That is, the i th bit of the initial challenge d ₂ indicates whether it is necessary to use g ₂ , and in this way, the i th bit of the initial challenge d _m indicates whether or not it is necessary to use g _m . As such, it is required to retrieve each of the commitments R within the signature appendix.

Furthermore, one triplet or multiple triplets should be linked to the message M. By hashing all of the commitments R and the message M, a hashing code is obtained that can recover each challenge d.

The same d = d ₁ , d ₂ , ..., d _m as extracted from the resulting hash (M, R) _.

If the appendix does not have a challenge , the verify operation begins with a recovery phase of one or more challenges d ⁿ by hashing all the commitments R and the message M.

D '= d' ₁ , d ' ₂ , ..., d' _m extracted from the resulting hash (M, R).

Next, as long as each triplet is consistent (an appropriate relationship of the following types is authenticated) and acceptable (must be compared by nonzero value). The controller accepts the signed message.

If the appendix does not include a commitment, the check operation begins with restoring one or more commitments R 'according to the appropriate one of the following two equations. There is no zero-established commitment.

The controller must then hash all of the commitments R 'and the message M to reconstruct each challenge d.

The same d = d ₁ , extracted from the resulting hash (M, R), d ₂ , ..., d _m

As long as each challenge reconstructed is the same as the corresponding challenge in the appendix, the controller accepts each signed message.

The present invention relates to methods, systems, and apparatuses for verifying the authenticity of an entity and / or the integrity and / or authenticity of a message.

Claims (29)

delete delete delete delete delete delete delete delete delete delete delete delete delete delete delete delete delete delete Each pair of keys in (Q _i , G _i ) is G _i × Q _i ^v = 1 mod n or G _i = Obtaining at least one secret value Q ₁ , Q ₂ , ..., Q _m and each published value G ₁ , G ₂ , ..., G _m satisfying the formula of Q _i ^v mod n Where m is an integer greater than or equal to 1 and i is an integer between 1 and m, where n is a public integer such as the product of _f prime factors p ₁ , p ₂ , ..., p _f , of which At least two prime factors are different, where f is an integer greater than 1, where v is a public exponent of the form v = 2 ^k , where k is a security parameter with an integer value greater than 1 (sequrity parameter), where each public value G _i (i = 1,2, ..., m) satisfies G _i = g _i ² mod n, where g _i (i = 1,2 , ..., m) is a radix with an integer value greater than 1 and less than each of the prime factors p ₁ , p ₂ , ..., p _f , where at least one integer having a value between 1 and m g _l or _(l -g) for the value of l is jeongsuhwan non-rechargeable or If a (non-quadratic residues) modulo (modulo) n, where for at least one integer s has a value between 1 and m q _s is any one of g _s mod n or (-g _s) mod n Not equal, where i = 1,2, ..., m where G _i × Q _i ^v = 1 mod n then q _i = Q _i ^{-v / 2} and G _i = Q _i ^v mod for n q _i = Q _i ^{v / 2} ; And Using at least the secret value of Q ₁ , Q ₂ ,..., Q _m in authentication or in a signature method. The method of claim 19, wherein the entity can be authenticated: Receiving a commitment R from a daemon, wherein the commitment R has a value calculated by the formula R = r ^v mod n, where r is greater than 0 arbitrarily selected by the daemon and n Is a smaller integer; randomly selecting _m challenges d ₁ , d ₂ ,... d _m ; Transmitting the challenges d ₁ , d ₂ ,..., D _m to the daemon; Receiving an answer D from the daemon, where the answer D is D = r × Q ₁ ^d1 × Q ₂ ^d2 × ... × Q _m ^dm has a value calculated from the formula of mod n; And The pledge R and D ^v ×

×

× ... ×

checking that the daemon is true if answer D has a value such that mod n has the same value, where i = 1,2, ..., m, where G _i × Q _i ^v = 1 for mod n and ε _i = +1 and G _i = And in the case of Q _i ^v mod n, further comprising the step of ε _i = −1. The method of claim 19, wherein the entity can be authenticated: Receiving a promise R from a demonstrator, the promise R is a value calculated using a Chinese surplus method from a set of commitment components R _j at j = 1, 2, ..., f. Each pledge element R _j has a value that satisfies R _j = r _j ^v mod p _j , where r _j is an integer greater than 0 and less than p _j optionally selected by the daemon; randomly selecting _m challenges d ₁ , d ₂ , ..., d _m ; Transmitting the challenges d ₁ , d ₂ ,... D _m to the daemon; Receiving an answer D from the daemon, the answer D being calculated from a set of answer elements D _j using the Chinese excess method, wherein the answer elements D _j are j = 1, 2, ..., f D _j = r _j ×

×

× ... ×

It has a value satisfying a mod p _j, where i = 1,2, ..., m and j = 1,2, ..., when the f Q _{i, j} = Q _i mod p _j ; And The pledge R and D ^v ×

×

× ... ×

checking that the daemon is true if answer D has a value such that mod n has the same value, where i = 1,2, ..., m, where G _i × Q _i ^v = 1 In case of mod n ε _i = +1 and G _i = And in the case of Q _i ^v mod n, further comprising the step of ε _i = −1. The method of claim 19, wherein the message can be authenticated: Receiving a token T from a daemon, wherein the token T has a value of T = h (M, R), where h is a hash function and M is a message sent from the daemon And R is a promise with a value calculated by the formula R = r ^v mod n, where r is an integer greater than 0 and less than n optionally selected by the daemon; randomly selecting _m challenges d ₁ , d ₂ , ..., d _m ; Transmitting the challenges d ₁ , d ₂ ,..., D _m to the daemon; Receiving an answer D from the daemon, where the answer D is D = r × Q_One ^d1× Q₂ ^d2× ... × Q_m ^dm has a value satisfying mod n; And The tokens T and h (M, D ^v ×

×

× ... ×

checking that the message M is true if answer D has a value such that the value of mod n) is the same, where i = 1,2, ..., m, where G _i × Q _i ^v = For 1 mod n ε _i = +1 and G _i = And in the case of Q _i ^v mod n, further comprising the step of ε _i = −1. The method of claim 19, wherein the message can be authenticated: Receiving a token T from a daemon, wherein the token T has a value of T = h (M, R), where h is a hash function, M is a message sent from the daemon, and R is j = 1,2, ..., a commitment has a value that is calculated using the difference between the excess varnish method from a set of commitment factors r _j in f, each commitment factors r _j is ^{_{r j = r j v mod p}} j Has a value satisfying r _j , wherein r _j is an integer greater than 0 and less than p _j arbitrarily selected by the daemon; randomly selecting _m challenges d ₁ , d ₂ , ..., d _m ; Transmitting the challenges d ₁ , d ₂ ,..., D _m to the daemon; Receiving an answer D from the daemon, the answer D being calculated from a set of answer elements D _j using the Chinese excess method, wherein the answer elements D _j are j = 1, 2, ..., f D _j = r _j ×

×

× ... ×

It has a value satisfying a mod p _j, where i = 1,2, ..., m and j = 1,2, ..., when the f Q _{i, j} = Q _i mod p _j ; And The tokens T and h (M, D ^v ×

×

× ... ×

checking that the message M is true if answer D has a value such that the value of mod n) is the same, where i = 1,2, ..., m, where G _i × Q _i ^v = For 1 mod n ε _i = +1 and G _i = And in the case of Q _i ^v mod n, further comprising the step of ε _i = −1. The method of claim 20, wherein the method is And the challenge is 0 ≦ d _i ≦ 2 ^k −1 at i = 1,2, ..., m. The method of claim 19, wherein the signatory can sign the message, randomly selecting m integers r _i greater than 0 and less than n at i = 1, 2, ..., m; calculating a promise R _i having a value of R _i = r _i ^v mod n at i = 1,2, ..., m; Calculating a token T having a value of T = h (M, R ₁ , R ₂ , ..., R _m ), where M is the message to be signed and h is a binary train of m bits ( a hash function that generates a binary train; Identifying the d ₁ , d ₂ , ..., d _m bits of the token T; And and calculating the answer D _i = r _i × Q _i ^di at i = 1,2, ..., m. The method of claim 25, so that the signature can be verified, collecting the token T and the answer D _i at i = 1,2, ..., m; And Token T and h (M, D ₁ ^v ×

mod n, D ₂ ^v ×

mod n, ..., D _m ^v ×

checking that the message M is true if answer D has a value such that the value of mod n) is the same, where i = 1,2, ..., m, where G _i × Q _i ^v = For 1 mod n ε _i = +1 and G _i = And in the case of Q _i ^v mod n, further comprising the step of ε _i = −1. Memory for storing a set of instructions; And In a system comprising a processor coupled with a memory to execute the set of instructions stored in the memory, the instructions include: Each pair of (Q _i , G _i ) keys is G _i × Q _i ^v = 1 mod n equation or G _i = To obtain a set of one or more secret values Q ₁ , Q ₂ , ..., Q _m, and each published value G ₁ , G ₂ , ..., G _m , satisfying one of the equations Q _i ^v mod n Steps, where m is an integer greater than or equal to 1, i is an integer between 1 and m, where n is a product such as the product of the f secret prime factors specified by p ₁ , p ₂ , ..., p _f Is an integer, and at least two said prime factors are different, where f is an integer greater than 1, where v is a public exponent such that v = 2 ^k , where k is an integer value greater than 1 Is a security parameter, where each public value G _i (i = 1,2, ..., m) satisfies G _i = g _i ² mod n, where g _i (i = 1,2, ..., m) is a base number with an integer value greater than 1 and less than each prime factor p ₁ , ..., p _f , where at least a value between 1 and m for one integer l _l g, or -g _l is jeongsuhwan Non-rechargeable and remainder into n (non-quadratic residues) module, here having a value between 1 and m which at least one of q _s to the integer s is g _s mod n or (-g _s) mod n Not equal, where i = 1,2, ..., m where G _i × Q _i ^v = 1 mod n then q _i = Q _i ^{-v / 2} and G _i = Q _i ^v mod for n q _i = Q _i ^{v / 2} ; And And using at least the secret value of Q ₁ , Q ₂ ,..., Q _m in authentication or in a signature method. Each pair of (Q _i , G _i ) keys is G _i × Q _i ^v = 1 mod n equation or G _i = To obtain a set of one or more secret values Q ₁ , Q ₂ , ..., Q _m, and each published value G ₁ , G ₂ , ..., G _m , satisfying one of the equations Q _i ^v mod n Steps, where m is an integer greater than or equal to 1, i is an integer between 1 and m, where n is a product such as the product of the f secret prime factors specified by p ₁ , p ₂ , ..., p _f Is an integer and at least two said prime factors are different, where f is an integer greater than 1, where v is a public exponent such as v = 2 ^k , where k is a security parameter with an integer value greater than 1 , Where each public value G _i (i = 1,2, ..., m) satisfies G _i = g _i ² mod n, where g _i (i = 1,2, ..., m) is a radix whose integer value is greater than 1 and less than each prime factor p ₁ , ..., p _f , where g _l or -g for at least one integer value l having a value between 1 and m _l is the jeongsuhwan non-rechargeable remaining (non-quadratic residues) Dyulro wherein n, where for at least one integer s has a value between 1 and m are q _s g _s mod n or (-g _s) mod n with any degree without matches, where i = 1 , 2, ..., m days when ^{_{G i × Q i v = 1}} mod n case q _i = Q _i ^{-v / 2} and G _i = Q _i ^v mod n in the case of q _i = Q _i ^{v / 2} ; And A computer-readable storage medium storing instructions executed to cause a processor to execute according to the step of using at least the secret values of Q ₁ , Q ₂ , ..., Q _m in authentication or in a signature method. In a process using a computer to generate an asymmetric cryptographic key, the key is a secret value Q ₁ , Q ₂ , ..., Q _m and m public values G ₁ , G ₂ ,. The computer-implemented process comprising .., G _m , includes: Selecting a security parameter k that is an integer greater than one; Examining modulus n, where n is a public integer such as the product of at least two prime factors p ₁ , p ₂ , ..., p _f ; selecting _m bases g ₁ , g ₂ , ..., g _m , where g _i (i = 1,2, ..., m) is greater than 1 and each prime factor p ₁ , ... is a radix with an integer value less than, p _f , where g _l or (-g _l ) for at least one integer value l between 1 and m Is a non-quadratic residues modulo n of the integer ring; when i = 1,2, ..., m G _i = g _i ² calculating the public value G _i by mod n; And G _i .Q _i ^v = 1 mod n or G _i when i = 1,2, ..., m Calculating the secret value Q _i by one of the formulas Q _i ^v mod n, wherein the open index v is equal to v = 2 ^k , where at least one integer having a value between 1 and m For the value s q _s does not match either g _s mod n or (-g _s ) mod n, where G _i × Q _i ^v = 1 when i = 1,2, ..., m For mod n, q _i = Q _i ^{-v / 2} and for G _i = Q _i ^v mod n, asymmetric cryptographic keys are computer-implemented processes that include the steps q _i = Q _i ^{v / 2} . Process using computer to create.

Images