New embedded S

Download 1.14 Mb.
Date conversion17.10.2016
Size1.14 Mb.
1   ...   17   18   19   20   21   22   23   24   ...   31


A number of protocols can be defined over elliptic curves. This document will refer to the most widespread: Elliptic Curve Digital Signature Algorithm (ECDSA) [ansi962][fips186][ieee][rfc], Elliptic Curve Diffie-Hellman (ECDH) [ansi963][ieee][rfc], Elliptic Curve Menesez-Qu-Vanstone (ECMQV) [ansi963][ieee], Elliptic Curve Integrated Encryption Standard (ECIES).

ECDH is an analogue of the common Diffie-Hellman key exchange, with the same purpose. The pseudocode that describes ECDH algorithm is the following:

  1. Alice and Bob share the domain parameters T=(q, a, b, P, n, h)

  2. Alice generates randomly and calculates

  3. Bob generates randomly and calculates

  4. Alice e Bob exchange (they are called ephemeral keys)

  5. Alice calculates

  6. Bob calculates

  7. Alice e Bob share: in particular the shared secret is the x – coordinate of the point just obtained.

The ECDSA algorithm is a digital sign algorithm analogue to the common DSA algorithm: this signature scheme is a standard that is recognized from NIST and IEEE. The pseudocode that describes ECDSA algorithm is the following:
INPUT: domain parameters, message to sign m



  • randomly

  • If back to the beginning

  • has been used an hash function

  • ; if back to the beginning

  • Return (s,r)


  • otherwise reject

  • and

  • ; If reject

  • If accept, otherwise reject.


This protocol is secure if ECDLP is untreatable and the hash function is strong; the parameter k is called per message secret and must be generated and destroyed immediately after: if k was known it would be easy to derive the private key. - Message Encryption

ElGamal is an encryption protocol based on DLP. Thus ECDH problem is equivalent to solving the problem of decrypting simple encryption scheme ciphertexts. Since ECDH is equivalent to EC El Gamal, we immediately can infer the equivalence of the problem of decrypting EC EL Gamal ciphertexts and decrypting simple encryption scheme ciphertexts. If Alice wants to send Bob a message encrypted with ElGamal, Bob has to set up a public key as follows. He picks an elliptic curve defined over a finite field such that the DLP is hard for the group E(). He chooses a point on such that the order of is (divisible by) a large prime. He picks a random integer s and computes . Bob’s public key then is , his private key is the integer s.
Table - The ElGamal public key cryptosystem.




Alice picks a random integer and computes as well as , and sends to Bob

Bob decrypts the message by computing

This works because. If Alice uses the same “random” integer for two messages and , and if Eve knows the plaintext , then she can compute . (Shamir’s no-key protocol) - Message Encryption

The following cryptosystem was described in an unpublished mansucript of Shamir; it is also called Massey-Omura, and was first discovered by M. Williamson but not published since he was working at the GCHQ (a British Intelligence service) at the time.

Table explains the protocol, which is clearly based on the difficulty of the discrete log problem. The advantage of Shamir’s no-key protocol is the fact that no keys are involved; the main disadvantage is that for sending one message, Alice has to send two ciphertexts, and wait for Bob’s ciphertext to arrive.

Here Alice and Bob agree on an elliptic curve defined over a finite field , where is chosen in such a way that the DLP in is hard. They compute the group order and use a method for embedding messages as points on the elliptic curve . Then they basically follow the classical protocol of Shamir:
Table - Massey-Omura




Alice and Bob agree upon

Alice picks with

Alice computes and sends to Bob

Alice computes and sends to Bob

Bob picks a pair with

Bob computes and sends to Alice

Bob decrypts the message by computing

In fact, since etc. - Message Encryption

This protocol, which was suggested by Koyama, Maurer, Okamoto & Vanstone, works as follows. Alice picks primes and forms the RSA-key . It is easy to see that for all primes and elliptic curves over . Her public encryption key is a random integer chosen coprime to , and her private decryption key is computed via . Although is not a group, it is still true that for (almost) all points on .
For sending a message to Alice, Bob computes and computes on the elliptic curve ; then he sends the pair to Alice, who decrypts it by computing on and recovers the original message by dropping the last 10 bits. - Message Encryption

Let be an elliptic curve over , and let denote a quadratic nonresidue . Then the cubic can be brought into Weierstrass form by multiplying through with ands setting : this gives . The elliptic curve is called a quadratic twist of .
It is an easy exercise to show that if , then . Moreover, if is not the -coordinate of a point on , then it is the -coordinate of a point on . For a point , let denote the -coordinate of the point .
Now Alice chooses an RSA-modulus and an elliptic curve defined over . She also finds quadratic nonresidues and , and defines the quadratic twists , and . Let be an integer coprime to the groups orders of these four curves (i.e., coprime to and ). In order to encrypt a message , she first computes and ; if both symbols are positive, then is the -coordinate of some point . and , then is the -coordinate of some point etc. Bob now computes and sends to Alice. For decrypting the message, Alice sets

where . Then she computes and decrypts the message via . blind signature scheme

The blind signature scheme is a protocol for obtaining a signature from a signer, but the signer can neither learn the messages nor see the signatures the recipients obtain afterwards. In proxy signature scheme, the original signer delegates his signing capacity to a proxy signer who can sign a message submitted on behalf of the original signer. A verifier can validate its correctness and can distinguish between a normal signature and a proxy signature. In multi-proxy signature scheme, an original signer is allowed to authorize a group of proxy members to generate the multi signature on behalf of the original signer.

A proxy blind signature scheme is a digital signature scheme that ensures the properties of proxy signature and blind signature. In a proxy blind signature, an original signer delegates his signing capacity to proxy signer. A proxy blind signature scheme is a special form of blind signature which allows a designated person called proxy signer to sign on behalf of two or more original signers without knowing the content of the message or document. It combines the advantages of proxy signature, blind signature and multi-signature.
A proxy blind signature scheme consists of the following three phases:

  • Proxy key generation

  • Proxy blind multi-signature scheme

  • Signature verification

Most of the proxy blind signature schemes were developed based on the mathematical hard problems integer factorization (IFP) and simple discrete logarithm (DLP) which take sub-exponential time to solve. Alghazzawi et al. [7] describe a simple proxy blind signature scheme based on Elliptic Curve Discrete Logarithm Problem (ECDLP), which is solved in fully-exponential time. The algorithms for solving the ECDLP become infeasible much more rapidly as the problem size increases more than those algorithms for the IFP and DLP. Thus, ECC offers security equivalent to RSA and DSA while using far smaller key sizes. The benefits of this higher-strength per-bit include higher speeds, lower power consumption, bandwidth savings, storage efficiencies, and smaller certificates. This can be implemented in low power and small processor mobile devices such as smart card, PDA etc. which work in low power and small processor. Protocol

The protocol involves three entities:

  • Original signer S,

  • Proxy signer s P and

  • Verifier V.

It is described as follows.
Proxy Phase

  • Proxy generation:

The original signer S selects random integer k in the interval . Computes and . Where is regarded as an integer between 0 and q–1, then computes and computes .

  • Proxy delivery:

The original signer S sends to the proxy signer and make public.

  • Proxy Verification:

After receiving the secret key pairs , the proxy signer checks the validity of the secret key pairs with the following equation.

Signing Phase

  • The Proxy signer chooses random integer and computes and sends it to the verifier V.

  • After receiving the verifier chooses randomly and computes the following




and verifier V sends e to the proxy signer Ps.

  • After receiving e, Ps computes the following


and sends it to V.

  • Now V computes (6)

The tuples is the proxy blind signature.
Verification Phase
The verifier V computes the following equation.

 (7)

and verifies the validity of proxy blind signature with the equality . blind multi-signature scheme

Kar [6] describes an efficient proxy blind multi-signature scheme. It satisfies the security properties of both proxy and blind signature scheme. In the proposed scheme the security is based on the difficulty of breaking the one-way hash function and the elliptic curve discrete logarithm problem (ECDLP). Signatures can only be generated during valid delegation period. A trusted third party called certificate authority is utilized to ensure that. properties

The security properties for a secure blind multi-signature scheme are as follows:

  • Distinguishability: The proxy blind multi-signature must be distinguishable from the ordinary signature.

  • Strong unforgeability: Only the designated proxy signer can create the proxy blind signature for the original signer.

  • Non-repudiation: The proxy signer cannot claim that the proxy signer is disputed or illegally signed by the original signer.

  • Verifiability: The proxy blind multi-signature can be verified by everyone. After verification, the verifier can be convinced of the original signer's agreement on the signed message.

  • Strong undeniably: Due to fact that the delegation information is signed by the original signer and the proxy signature are generated by the proxy signer's secret key. Both the signer cannot deny their behaviour.

  • Unlinkability: When the signer is revealed, the proxy signer cannot identify the association between the message and the blind signature he generated.

  • Secret key dependencies: Proxy key or delegation pair can be computed only by the original signer's secret key.

  • Prevention of misuse: The proxy signer cannot use the proxy secret key for purposes other than generating valid proxy signatures. In case of misuse, the responsibility of the proxy signer should be determined explicitly.
1   ...   17   18   19   20   21   22   23   24   ...   31

The database is protected by copyright © 2016
send message

    Main page