The discrete logarithm problem is as follows: given a generator of a finite group and a random element , find the (unique) integer such that . In cryptography, we are interested in groups for which the discrete logarithm problem (Dlog for short) is assumed to be hard (or other discrete-log type assumptions like CDH and DDH). The two most common classes are a prime subgroup of the group for a large , and some Elliptic curve groups.
We provide the implementation of the most important Dlog groups in cryptography (see diagram below):
- Elliptic curve over the field
- Elliptic curve over the field
Although Elliptic curves groups look very different, the discrete log problem over them can be described as follows. Given an elliptic curve over a finite field , a base point on that curve (i.e., a generator of the group defined from the curve), and a random point on the curve, the problem is to find the integer such that .
We have currently incorporated the elliptic curves recommended by NIST.
The root of the family is a general Dlog Group that presents functionality that all Dlog Groups should implement.
At the second level we encounter three interfaces:
- PrimeOrderSubGroup: The order of the group must be a prime.
- DlogZp: Dlog Group over the field.
- DlogEllipticCurve: Any elliptic curve.
At the third level we have:
- DlogZpSafePrime: The order is not only a prime but also is such that prime .
- DlogEcFp: Any elliptic curve over .
- DlogEcF2m: Any elliptic curve over .
All these are general interfaces. Specifically, we implement Dlog Groups that are of prime order; therefore all the concrete classes presented here implement this interface. Other implementations may choose to add Dlog Groups that are not of prime order, and they are at liberty of doing so. They just need not to declare that they implement the PrimeOrderSubGroup interface.
We also see in the diagram two other interfaces that are used by DlogGroup:
- public GroupElement getGenerator()¶
The generator g of the group is an element of the group such that, when written multiplicatively, every element of the group is a power of g.
Returns: the generator of this Dlog group
- public GroupElement createRandomGenerator()¶
Creates a random generator of this Dlog group
Returns: the random generator
- public BigInteger getOrder()¶
Returns: the order of this Dlog group
- public GroupParams getGroupParams()¶
GroupParams is a structure that holds the actual data that makes this group a specific Dlog group. For example, for a Dlog group over Zp* what defines the group is p.
Returns: the GroupParams of that Dlog group
- public String getGroupType()¶
Each concrete class implementing this interface returns a string with a meaningful name for this type of Dlog group. For example: “elliptic curve over F2m” or “Zp*”
Returns: the name of the group type
- public GroupElement getIdentity()¶
Returns: the identity of this Dlog group
- public GroupElement exponentiate(GroupElement base, BigInteger exponent)¶
Raises the base GroupElement to the exponent. The result is another GroupElement.
- base –
- exponent –
the result of the exponentiation
- public GroupElement exponentiateWithPreComputedValues(GroupElement base, BigInteger exponent)¶
Computes the product of several exponentiations of the same base and distinct exponents. An optimization is used to compute it more quickly by keeping in memory the result of h1, h2, h4,h8,... and using it in the calculation.
Note that if we want a one-time exponentiation of h it is preferable to use the basic exponentiation function since there is no point to keep anything in memory if we have no intention to use it.
- base –
- exponent –
the exponentiation result
- public void endExponentiateWithPreComputedValues(GroupElement base)¶
This function cleans up any resources used by exponentiateWithPreComputedValues for the requested base. It is recommended to call it whenever an application does not need to continue calculating exponentiations for this specific base.
- base –
- public GroupElement simultaneousMultipleExponentiations(GroupElement groupElements, BigInteger exponentiations)¶
Computes the product of several exponentiations with distinct bases and distinct exponents. Instead of computing each part separately, an optimization is used to compute it simultaneously.
- groupElements –
- exponentiations –
the exponentiation result
- public GroupElement getInverse(GroupElement groupElement)¶
Calculates the inverse of the given GroupElement.
- groupElement – to invert
the inverse element of the given GroupElement
- public GroupElement createRandomElement()¶
Creates a random member of this Dlog group
Returns: the random element
- public GroupElement generateElement(boolean bCheckMembership, BigInteger... values)¶
This function allows the generation of a group element by a protocol that holds a Dlog Group but does not know if it is a Zp Dlog Group or an Elliptic Curve Dlog Group. It receives the possible values of a group element and whether to check membership of the group element to the group or not.
It may be not necessary to check membership if the source of values is a trusted source (it can be the group itself after some calculation). On the other hand, to work with a generated group element that is not really an element in the group is wrong. It is up to the caller of the function to decide if to check membership or not. If bCheckMembership is false always generate the element. Else, generate it only if the values are correct.
- bCheckMembership –
- values –
the generated GroupElement
- public boolean isGenerator()¶
Checks if the element set as the generator is indeed the generator of this group.
Returns: true if the generator is valid, false otherwise.
- public boolean isMember(GroupElement element)¶
Checks if the given element is a member of this Dlog group
- element – possible group element for which to check that it is a member of this group
true if the given element is a member of this group, false otherwise.
- public boolean validateGroup()¶
Checks parameters of this group to see if they conform to the type this group is supposed to be.
Returns: true if valid, false otherwise.
- public boolean isOrderGreaterThan(int numBits)¶
Checks if the order of this group is greater than 2^numBits
- numBits –
true if the order is greater than 2^numBits, false otherwise.
- public boolean isPrimeOrder()¶
Checks if the order is a prime number
Returns: true if the order is a prime number, false otherwise.
- public GroupElement reconstructElement(boolean bCheckMembership, GroupElementSendableData data)¶
Reconstructs a GroupElement given the GroupElementSendableData data, which might have been received through a Channel open between the party holding this DlogGroup and some other party.
- bCheckMembership – whether to check that the data provided can actually reconstruct an element of this DlogGroup. Since this action is expensive it should be used only if necessary.
- data – the GroupElementSendableData from which we wish to “reconstruct” an element of this DlogGroup
the reconstructed GroupElement
- public GroupElement encodeByteArrayToGroupElement(byte binaryString)¶
This function takes any string of length up to k bytes and encodes it to a Group Element. k can be obtained by calling getMaxLengthOfByteArrayForEncoding() and it is calculated upon construction of this group; it depends on the length in bits of p.
The encoding-decoding functionality is not a bijection, that is, it is a 1-1 function but is not onto. Therefore, any string of length in bytes up to k can be encoded to a group element but not every group element can be decoded to a binary string in the group of binary strings of length up to 2^k.
Thus, the right way to use this functionality is first to encode a byte array and then to decode it, and not the opposite.
- binaryString – the byte array to encode
the encoded group Element or null if the string could not be encoded
- public byte decodeGroupElementToByteArray(GroupElement groupElement)¶
This function decodes a group element to a byte array. This function is guaranteed to work properly ONLY if the group element was obtained as a result of encoding a binary string of length in bytes up to k.
This is because the encoding-decoding functionality is not a bijection, that is, it is a 1-1 function but is not onto. Therefore, any string of length in bytes up to k can be encoded to a group element but not any group element can be decoded to a binary sting in the group of binary strings of length up to 2^k.
- groupElement – the element to decode
the decoded byte array
- public int getMaxLengthOfByteArrayForEncoding()¶
This function returns the value k which is the maximum length of a string to be encoded to a Group Element of this group. Any string of length k has a numeric value that is less than (p-1)/2. k is the maximum length a binary string is allowed to be in order to encode the said binary string to a group element and vice-versa. If a string exceeds the k length it cannot be encoded.
Returns: k the maximum length of a string to be encoded to a Group Element of this group. k can be zero if there is no maximum.
- public byte mapAnyGroupElementToByteArray(GroupElement groupElement)¶
This function maps a group element of this dlog group to a byte array. This function does not have an inverse function, that is, it is not possible to re-construct the original group element from the resulting byte array.
Returns: a byte array representation of the given group element
- public GroupElementSendableData generateSendableData()¶
This function is used when a group element needs to be sent via a edu.biu.scapi.comm.Channel or any other means of sending data (including serialization). It retrieves all the data needed to reconstruct this Group Element at a later time and/or in a different VM. It puts all the data in an instance of the relevant class that implements the GroupElementSendableData interface.
Returns: the GroupElementSendableData object
- public boolean isIdentity()¶
checks if this element is the identity of the group.
Returns: true if this element is the identity of the group, false otherwise.
// initiate a discrete log group (in this case the OpenSSL implementation of the elliptic curve group K-233) DlogGroup dlog = new OpenSSLDlogECF2m("K-233"); SecureRandom random = new SecureRandom(); // get the group generator and order GroupElement g = dlog.getGenerator(); BigInteger q = dlog.getOrder(); BigInteger qMinusOne = q.subtract(BigInteger.ONE); // create a random exponent r BigInteger r = BigIntegers.createRandomInRange(BigInteger.ZERO, qMinusOne, random); // exponentiate g in r to receive a new group element GroupElement g1 = dlog.exponentiate(g, r); // create a random group element GroupElement h = dlog.createRandomElement(); // multiply elements GroupElement gMult = dlog.multiplyGroupElements(g1, h);