2011-08-30 17:32:46 +02:00
|
|
|
Cryptic 1.1.1
|
2010-12-09 23:22:44 +01:00
|
|
|
|
2011-02-22 23:17:01 +01:00
|
|
|
Copyright (c) 2009-2011 Entr'ouvert
|
|
|
|
Copyright (c) 2009 Ates Mikael
|
|
|
|
All rights reserved.
|
2010-12-09 23:22:44 +01:00
|
|
|
|
2011-02-22 23:17:01 +01:00
|
|
|
INTRODUCTION
|
|
|
|
------------
|
2010-12-09 23:22:44 +01:00
|
|
|
|
2011-02-22 23:17:01 +01:00
|
|
|
Cryptic - Cryptographic tools and protocols
|
2010-12-09 23:22:44 +01:00
|
|
|
|
2011-02-22 23:17:01 +01:00
|
|
|
Cryptic is a free software library released under the GNU GPL v2 and above
|
|
|
|
license.
|
|
|
|
|
|
|
|
Cryptic allows the implementation of digital certificates with advanced
|
|
|
|
properties. The goal is to ensure privacy for cross-organization exchanges of
|
|
|
|
certified data.
|
|
|
|
|
|
|
|
Cryptic is written in C language and depends on glib and openssl. Bindings for
|
|
|
|
the Python and Java languages are provided.
|
|
|
|
|
|
|
|
REPOSITORY
|
|
|
|
----------
|
|
|
|
|
|
|
|
* git@repos.entrouvert.org:cryptic.git
|
|
|
|
|
|
|
|
LISTS
|
|
|
|
-----
|
|
|
|
|
2011-08-30 17:32:46 +02:00
|
|
|
* Development: cryptic-devel@listes.entrouvert.com (archive)
|
|
|
|
* Git commits: cryptic-commits@listes.entrouvert.com (archive)
|
2011-02-22 23:17:01 +01:00
|
|
|
|
|
|
|
DESCRIPTION
|
|
|
|
-----------
|
|
|
|
|
|
|
|
Advanced certificates helps in reducing the certified information disclosed to
|
|
|
|
verifiers. The certificates have the following properties:
|
|
|
|
* Selective disclosure of content.
|
|
|
|
* Proofs on attributes contained in certificates.
|
|
|
|
* Unlinkability between certificate issuing and showing transactions.
|
|
|
|
|
|
|
|
The Cryptic library can be used to create at a low-level certificates with the
|
|
|
|
properties previously enumerated. The certificate formatting, in XML or ASN1
|
|
|
|
for instance, is not handled in Cryptic.
|
|
|
|
|
|
|
|
The goal is a fine-grained information disclosure for off-line certificates.
|
|
|
|
Such certificates may be used multiple times without re-issuing. When a
|
|
|
|
certificate is issued on demand, it is trivial to make it includes only the
|
|
|
|
needed information. However, when the certificate is already issued, it is
|
|
|
|
useful to have means to select which signed information is revealed. For
|
|
|
|
instance, the selective disclosure allows to reveal a date of birth and not a
|
|
|
|
place of birth both contained in the same certificate. A range proof allows to
|
|
|
|
only reveal that the certificate prover is of age and not reveal the date of
|
|
|
|
birth contained in the certificate.
|
|
|
|
|
|
|
|
A certificate is said 'proved' because a secret is included in the
|
|
|
|
certificate. To only show a certificate require to prove to verifier that the
|
|
|
|
secret is known without revealing it. (It is similar to prove the knowledge of
|
|
|
|
a private key making a signature. In a way, the public key is proved as a
|
|
|
|
certificate is proved.)
|
|
|
|
|
|
|
|
Certificate holder is a term usually avoided because it may refer to bearer
|
|
|
|
tokens. Holder may be used if it is taken as a synomous to know the secret of
|
|
|
|
the certificate hold.
|
|
|
|
|
|
|
|
Furthermore, the CL-Signature implementation allows the unlinkability of a
|
|
|
|
certificate issued with this certificate shown to verifiers. In other words,
|
|
|
|
the certificate signature can not be used as a factor of linkability between
|
|
|
|
to transactions involving a same certificate. (But many other factors may be
|
|
|
|
used (time correlation, attribute contents, etc.), unlinkability is a huge
|
|
|
|
paradigm.)
|
|
|
|
|
|
|
|
The unlinkability may be expected when a user shows multiple times a same
|
|
|
|
certificate or between the issuing and showing transactions of this
|
|
|
|
certificate. The unlinkability of the user transactions is a strong property
|
|
|
|
of anonymity and ion some cases a privacy-preserving principle.
|
|
|
|
|
|
|
|
For instance, Cryptic can be used to implement e-cash and e-voting
|
|
|
|
architectures.
|
|
|
|
|
|
|
|
The library does not deal with storage and protocols, only computation.
|
|
|
|
|
|
|
|
OVERVIEW
|
|
|
|
--------
|
|
|
|
|
|
|
|
The library includes:
|
|
|
|
|
|
|
|
libcryptic.a:
|
|
|
|
Group generation
|
|
|
|
Prime order group
|
|
|
|
Quadratic residues group
|
|
|
|
|
|
|
|
Signature schemas
|
|
|
|
Camenisch-Lysyanskaya Signature (CL-Signature)
|
|
|
|
|
|
|
|
Proof of Knowledge
|
|
|
|
Schnorr zero-knowledge proof of knowledge protocol.
|
|
|
|
Range proofs on integers
|
|
|
|
|
|
|
|
INSTALLATION
|
|
|
|
------------
|
|
|
|
|
|
|
|
Please check the Makefile before compiling.
|
|
|
|
Then,
|
2010-12-09 23:22:44 +01:00
|
|
|
autogen.sh
|
|
|
|
make
|
2011-02-22 23:17:01 +01:00
|
|
|
make check
|
2010-12-09 23:22:44 +01:00
|
|
|
make install
|
|
|
|
|
2011-02-22 23:17:01 +01:00
|
|
|
QUICK START
|
|
|
|
-----------
|
|
|
|
|
2011-08-30 17:49:11 +02:00
|
|
|
See tests/tests.c, bindings/python/samples.py,
|
2011-02-22 23:17:01 +01:00
|
|
|
bindings/java/Myclass.java
|
|
|
|
|
|
|
|
BITS OF DOCUMENTATION
|
|
|
|
---------------------
|
|
|
|
|
|
|
|
*** Error Codes ***
|
|
|
|
|
|
|
|
Error codes are listed in error.h.
|
|
|
|
- Functions return a negative error code on failure and 0 either
|
|
|
|
- Except verification functions that return 1 on success and <= 0 on
|
|
|
|
failure
|
|
|
|
- Getters return NULL if no member
|
|
|
|
Take care that functions cryptic_clsig_load_certificate* verify the
|
|
|
|
signatures but return 0 on success including the checking of a valid
|
|
|
|
signature.
|
|
|
|
|
|
|
|
*** Generic helper functions ***
|
|
|
|
|
|
|
|
Many helper functions are defined in utils.h
|
|
|
|
|
|
|
|
*** Maths directory ***
|
|
|
|
|
|
|
|
Class: CrypticPrimeOrderGroup
|
|
|
|
|
|
|
|
Allows to create a prime order group.
|
|
|
|
This kind of group can be used for zero knowledge proofs of knowledge.
|
|
|
|
|
|
|
|
The group has prime modulus p. p is a safe prime.
|
|
|
|
p = 2pp + 1 with pp also prime.
|
|
|
|
The generator of the group is g.
|
|
|
|
|
|
|
|
To create a prime order group with a modulus of size 512 bits:
|
|
|
|
CrypticPrimeOrderGroup *g = NULL;
|
|
|
|
g = cryptic_prime_order_group_new(512);
|
|
|
|
|
|
|
|
The classe has a member that is a table of generators that may be used as
|
|
|
|
bases for proofs. This table is filled with the function
|
|
|
|
cryptic_prime_order_group_more_bases().
|
|
|
|
For instance, cryptic_prime_order_group_more_bases(g,10);
|
|
|
|
|
|
|
|
Class: CrypticQRG
|
|
|
|
|
|
|
|
Allows to create a quadratic residues group.
|
|
|
|
Such a group is used by the Camenisch-Lysyanskaya signature.
|
|
|
|
|
|
|
|
Two safe primes p and q. p = 2pp +1 and q = 2qq +1
|
|
|
|
n = pq
|
|
|
|
The QRG is the multiplicative group Z_n^*
|
|
|
|
The order is pp*qq
|
|
|
|
A base (a quadratic residue) is picked from the group:
|
|
|
|
From a random r of size n:
|
|
|
|
qr = r^2 mod n and qr != 1 and coprime(qr-1,n)
|
|
|
|
|
|
|
|
Other quadratic residues are generated from the first picked.
|
|
|
|
With a random of size the group order:
|
|
|
|
New_qr = qr^rand mod n
|
|
|
|
|
|
|
|
Functions to pick qrs:
|
|
|
|
int cryptic_qrg_pick_base(CrypticQRG *qrg, BIGNUM *out_base);
|
|
|
|
int cryptic_qrg_pick_k_bases(CrypticQRG *qrg, BIGNUM **out_bases,
|
|
|
|
int nb_bases);
|
|
|
|
|
|
|
|
Class: CrypticDecomposeInteger
|
|
|
|
|
|
|
|
Decompose an integer in four squares.
|
|
|
|
Used in range proofs.
|
|
|
|
|
|
|
|
CrypticDecomposeInteger* decomposition = NULL;
|
|
|
|
decomposition = cryptic_decompose_integer_new(numToDecompose);
|
|
|
|
cryptic_print_bn("first square: ", decomposition->a);
|
|
|
|
cryptic_print_bn("second square: ", decomposition->b);
|
|
|
|
cryptic_print_bn("thrid square: ", decomposition->c);
|
|
|
|
cryptic_print_bn("forth square: ", decomposition->d);
|
|
|
|
|
|
|
|
utils files
|
|
|
|
|
|
|
|
Basic functions.
|
|
|
|
Up to now, only random numbers are necessary.
|
|
|
|
- The random value is returned in parameter and an error code is returned:
|
|
|
|
int cryptic_find_random(BIGNUM *ret, int size);
|
|
|
|
int cryptic_find_random_with_range_value(BIGNUM *ret, BIGNUM *value);
|
|
|
|
- Without error code:
|
|
|
|
BIGNUM* cryptic_ret_random(int size);
|
|
|
|
BIGNUM* cryptic_ret_random_with_range_value(BIGNUM *value);
|
|
|
|
|
|
|
|
*** Protocols directory ***
|
|
|
|
|
|
|
|
** Schnorr proof of knowledge (pok_schnorr directory) **
|
|
|
|
|
|
|
|
Class: CrypticZkpkSchnorr
|
|
|
|
|
|
|
|
Used to lead Zero knowledge proof of knowledge with the Schnorr protocol.
|
|
|
|
Let g be the generator of a group of prime order q.
|
|
|
|
|
|
|
|
Assume that you know y=g^x and as a prover you want to prove that you know
|
|
|
|
x to the verifier who knows y without revealing x and the verifier learns
|
|
|
|
with a negligeable probability nothing about x.
|
|
|
|
You pick a random and send the commitment: t = g^r
|
|
|
|
The verifier challenges you with c
|
|
|
|
you prove that you know x responding: s = r - cx
|
|
|
|
The verifier check that t ?= y^c . g^s
|
|
|
|
Explanation: s = r -cx <=> r = s + cx
|
|
|
|
<=> g^r = g^s + g^cx <=> g^r = g^s + (g^x)^c
|
|
|
|
|
|
|
|
You can prove like this any discrete logarithm representation (DLREP).
|
|
|
|
A dlrep looks like dlrep = g1^q1 . ... . gi^qi
|
|
|
|
Then you want to prove that you know {q1,...,qi} to a verifier who knows
|
|
|
|
dlrep.
|
|
|
|
{g1,...,gi} are prime ordre group bases shared between the prover and the
|
|
|
|
verifier.
|
|
|
|
|
|
|
|
Both the prover and the verifier init their proof the same way
|
|
|
|
CrypticZkpkSchnorr* shn_prover = NULL;
|
|
|
|
shn_prover = cryptic_zkpk_schnorr_new(bases, nb_quantities, modulus);
|
|
|
|
|
|
|
|
The prover computes the commitment with
|
|
|
|
cryptic_zkpk_schnorr_round1(shn_prover);
|
|
|
|
and sends the commitment to the verifier shn_prover->commitment
|
|
|
|
The prover receives the challenge and compute the responses, one per
|
|
|
|
quantity to prove.
|
|
|
|
cryptic_zkpk_schnorr_round2(shn_prover, order, challenge, quantities);
|
|
|
|
and sends the responses to the verifier shn_prover->responses
|
|
|
|
The verifier verifies the proof with
|
|
|
|
cryptic_zkpk_schnorr_verify_interactive_proof(shn_verifier, dlrep,
|
|
|
|
commitment, challenge, responses);
|
|
|
|
|
|
|
|
The order to compute the responses in not mandatory. however if not used
|
|
|
|
the random must be >> cx to keep the zero knowledge. This is useful
|
|
|
|
because in some cases the verifier is not assumed to know the group order
|
|
|
|
with cryptic_zkpk_schnorr_round2_without_order()
|
|
|
|
|
|
|
|
You have noticed that the randoms used in the commitment are generated
|
|
|
|
into the function. However, in some cases you need to combine proofs to
|
|
|
|
prove statements on the same quantity in two different proofs. We you lead
|
|
|
|
this kind of proofs you must use the same random number in the two proofs
|
|
|
|
when you to prove that the quantity is the same. You deduce that the
|
|
|
|
answer will be the same for the two proofs.
|
2011-08-30 17:32:46 +02:00
|
|
|
The first round function can then be used with randoms given in
|
|
|
|
parameters.
|
2011-02-22 23:17:01 +01:00
|
|
|
You generate them by yourself and then give them in parameters arranged as
|
|
|
|
you want.
|
|
|
|
cryptic_zkpk_schnorr_round1_one_random_chosen(shn, random, position);
|
|
|
|
cryptic_zkpk_schnorr_round1_randoms_chosen(shn, randoms);
|
|
|
|
|
|
|
|
The proof previously presented is an interactive proof relying on a
|
|
|
|
challenge freshly generated by the verifier after the commitment.
|
|
|
|
Using the random oracle model played by a hash function, it is feasible
|
|
|
|
to realise a non-interactive proof.
|
|
|
|
The details on how to compute the hash are given later because the class
|
|
|
|
CrypticHashForNiProofs is dedicated for this purpose.
|
|
|
|
However th hash is tipically of the form of a concatenation
|
|
|
|
modulus || bases || dlrep || Commitment and then hashed.
|
|
|
|
Only the verifier function differs
|
|
|
|
cryptic_zkpk_schnorr_verify_noninteractive_proof(shn, dlrep, hash,
|
|
|
|
responses);
|
|
|
|
From the prover point of view, the prover needs to generate the hash and
|
|
|
|
give it as a parameter instead of the challenge to compute the responses.
|
|
|
|
|
|
|
|
*** Utils directory ***
|
|
|
|
|
|
|
|
print files
|
|
|
|
|
|
|
|
Function used to print bignums and display CLSIG structure parameters
|
2010-12-09 23:22:44 +01:00
|
|
|
|
2011-02-22 23:17:01 +01:00
|
|
|
AUTHOR
|
|
|
|
------
|
2010-11-18 11:31:04 +01:00
|
|
|
|
2011-02-22 23:17:01 +01:00
|
|
|
Mikaël Ates <mates@entrouvert.com>
|