**New here?**Learn about Bountify and follow @bountify to get notified of new bounties! Follow @bountify x

Simple library with signing, verifying, encryption and decryption of a 64-byte string of data with blind signatures. It should be using RSA or elliptic curves. If it can use openssl and/or PKCS11 for the actual crypto operations, that would be even better. If the data needs to be longer than 64 bytes for this to work, it can use deterministic padding.

Here is a flowchart of how the library is intended to be used: https://download.bitmessage.org/tmp/Blind%20signature%20flowchart%20(2).svg

Don't worry about how the data is transferred between the parties, that's outside of the scope. Same with creating keys, just assume that we can create keypairs, or simply re-use OpenSSL or PKCS11.

If you prefer C to python, that's ok as well as long as it calls OpenSSL or PKCS11.

The library must be able to be licensed under the MIT license (e.g. in case you're using third party code).

I'm not a crypto expert and it's possible I don't understand how it's supposed to work and what I'm asking for isn't possible. If that's the case, I need to know.

## 1 Solution

The way I understand it, the algorithm presented in your flowchart can't work.

```
Let:
e: The certifier's public key exponent (encryption)
d: The certifier's private key exponent (decryption)
n: The product of e and d
epsilon: The creator's ephemeral public key exponent
delta: The creator's ephemeral private key exponent
nu: The product of epsilon and delta
```

Working out the math, it might seem like the algorithm would work:

```
enc = m^epsilon (mod nu) (encryption: c = m^e (mod n))
encsig = (m^epsilon)^d (mod n) (signing: s = m^d (mod n))
sig = ((m^epsilon)^d)^delta (mod nu) (decryption: m = c^d (mod n))
= ((m^d)^epsilon)^delta (mod nu) (commutativity)
= m^d (mod n) ((m^e)^d = m (mod n))
(signing: s = m^d (mod n))
```

However, `n != nu`

, as `(e, d)`

and `(epsilon, delta)`

are different. Therefore, the properties don't hold.

The way blind signing is normally done (as shown here) is to use a random number to compute `m' = m*r^e (mod n)`

using the certifier's public key. Then the certifier signs that which gives `s' = (m')^d (mod n) = (m*r^e)^d (mod n)`

. For unblinding, `s'`

is divided by the same random number: `s = s' / r (mod n) = (m*r^e)^d / r (mod n)`

. As `(r^e)^d = r (mod n)`

, we get `s = m^d (mod n)`

, which is the signature we want.

Here is some code doing blind signing this way: https://stackoverflow.com/a/33982599. I've tried it and it works. I've adapted the code to follow the certifier/creator/validator structure, but I don't know if it would be of any use to you since it uses `pycrypto`

instead of OpenSSL.

**ECC Blind signature**

I found a paper showing a suitable ECC blind signature schema. It's a fair bit more complicated than your flowchart.

I suppose you ultimately want this to end up in PyBitmessage, so I went with `pyelliptic`

as a dependency, which PyBitmessagealready uses for ECC.

First, since `pyelliptic`

only includes the OpenSSL functions it uses, `pyelleptic/openssl.py`

needs to be modified to include new functions:

```
print("A bit of Python just to help the syntax highlighter")
# That goes in _OpenSSL's __init__ method
self.BN_CTX_new = self._lib.BN_CTX_new
self.BN_CTX_new.restype = ctypes.c_void_p
self.BN_CTX_new.argtypes = []
self.BN_dup = self._lib.BN_dup
self.BN_dup.restype = ctypes.c_void_p
self.BN_dup.argtypes = [ctypes.c_void_p]
self.BN_rand = self._lib.BN_rand
self.BN_rand.restype = ctypes.c_int
self.BN_rand.argtypes = [ctypes.c_void_p, ctypes.c_int, ctypes.c_int]
self.BN_set_word = self._lib.BN_set_word
self.BN_set_word.restype = ctypes.c_int
self.BN_set_word.argtypes = [ctypes.c_void_p, ctypes.c_ulong]
self.BN_mul = self._lib.BN_mul
self.BN_mul.restype = ctypes.c_int
self.BN_mul.argtypes = [ctypes.c_void_p, ctypes.c_void_p, ctypes.c_void_p, ctypes.c_void_p]
self.BN_mod_add = self._lib.BN_mod_add
self.BN_mod_add.restype = ctypes.c_int
self.BN_mod_add.argtypes = [ctypes.c_void_p, ctypes.c_void_p, ctypes.c_void_p, ctypes.c_void_p, ctypes.c_void_p]
self.BN_mod_inverse = self._lib.BN_mod_inverse
self.BN_mod_inverse.restype = ctypes.c_void_p
self.BN_mod_inverse.argtypes = [ctypes.c_void_p, ctypes.c_void_p, ctypes.c_void_p, ctypes.c_void_p]
self.BN_mod_mul = self._lib.BN_mod_mul
self.BN_mod_mul.restype = ctypes.c_int
self.BN_mod_mul.argtypes = [ctypes.c_void_p, ctypes.c_void_p, ctypes.c_void_p, ctypes.c_void_p, ctypes.c_void_p]
self.BN_lshift = self._lib.BN_lshift
self.BN_lshift.restype = ctypes.c_int
self.BN_lshift.argtypes = [ctypes.c_void_p, ctypes.c_void_p, ctypes.c_int]
self.BN_sub_word = self._lib.BN_sub_word
self.BN_sub_word.restype = ctypes.c_int
self.BN_sub_word.argtypes = [ctypes.c_void_p, ctypes.c_ulong]
self.BN_cmp = self._lib.BN_cmp
self.BN_cmp.restype = ctypes.c_int
self.BN_cmp.argtypes = [ctypes.c_void_p, ctypes.c_void_p]
self.BN_bn2dec = self._lib.BN_bn2dec
self.BN_bn2dec.restype = ctypes.c_char_p
self.BN_bn2dec.argtypes = [ctypes.c_void_p]
self.BN_CTX_free = self._lib.BN_CTX_free
self.BN_CTX_free.argtypes = [ctypes.c_void_p]
self.EC_GROUP_new_by_curve_name = self._lib.EC_GROUP_new_by_curve_name
self.EC_GROUP_new_by_curve_name.restype = ctypes.c_void_p
self.EC_GROUP_new_by_curve_name.argtypes = [ctypes.c_int]
self.EC_GROUP_get_order = self._lib.EC_GROUP_get_order
self.EC_GROUP_get_order.restype = ctypes.c_int
self.EC_GROUP_get_order.argtypes = [ctypes.c_void_p, ctypes.c_void_p, ctypes.c_void_p]
self.EC_GROUP_get_cofactor = self._lib.EC_GROUP_get_cofactor
self.EC_GROUP_get_cofactor.restype = ctypes.c_int
self.EC_GROUP_get_cofactor.argtypes = [ctypes.c_void_p, ctypes.c_void_p, ctypes.c_void_p]
self.EC_GROUP_get0_generator = self._lib.EC_GROUP_get0_generator
self.EC_GROUP_get0_generator.restype = ctypes.c_void_p
self.EC_GROUP_get0_generator.argtypes = [ctypes.c_void_p]
self.EC_POINT_copy = self._lib.EC_POINT_copy
self.EC_POINT_copy.restype = ctypes.c_int
self.EC_POINT_copy.argtypes = [ctypes.c_void_p, ctypes.c_void_p]
self.EC_POINT_add = self._lib.EC_POINT_add
self.EC_POINT_add.restype = ctypes.c_int
self.EC_POINT_add.argtypes = [ctypes.c_void_p, ctypes.c_void_p, ctypes.c_void_p, ctypes.c_void_p, ctypes.c_void_p]
self.EC_POINT_cmp = self._lib.EC_POINT_cmp
self.EC_POINT_cmp.restype = ctypes.c_int
self.EC_POINT_cmp.argtypes = [ctypes.c_void_p, ctypes.c_void_p, ctypes.c_void_p, ctypes.c_void_p]
self.EC_POINT_set_to_infinity = self._lib.EC_POINT_set_to_infinity
self.EC_POINT_set_to_infinity.restype = ctypes.c_int
self.EC_POINT_set_to_infinity.argtypes = [ctypes.c_void_p, ctypes.c_void_p]
```

Next, here's a crude demo showing the algorithm in action:

```
import os
from pyelliptic.openssl import OpenSSL
def ec_get_random(group, ctx):
order = OpenSSL.BN_new()
OpenSSL.EC_GROUP_get_order(group, order, ctx)
OpenSSL.BN_rand(order, OpenSSL.BN_num_bits(order), 0, 0)
return order
def ec_invert(group, a, ctx):
order = OpenSSL.BN_new()
OpenSSL.EC_GROUP_get_order(group, order, ctx)
m = OpenSSL.BN_num_bits(order)
inverse = OpenSSL.BN_mod_inverse(0, a, order, ctx)
return inverse
def ec_gen_keypair(group, ctx):
d = ec_get_random(group, ctx)
Q = OpenSSL.EC_POINT_new(group)
OpenSSL.EC_POINT_mul(group, Q, d, 0, 0, 0)
return (d, Q)
if __name__ == "__main__":
""" (1) Intialization """
# Field: F(2^283)
group = OpenSSL.EC_GROUP_new_by_curve_name(OpenSSL.get_curve("sect283r1"))
ctx = OpenSSL.BN_CTX_new()
# Order n
n = OpenSSL.BN_new()
OpenSSL.EC_GROUP_get_order(group, n, ctx)
# Identity O
O = OpenSSL.EC_POINT_new(group)
OpenSSL.EC_POINT_set_to_infinity(group, O)
# Generator G
G = OpenSSL.EC_GROUP_get0_generator(group)
# Certifier's keypair
keypair = ec_gen_keypair(group, ctx)
public = (group, G, n)
""" (2) Request """
# Signer: Random integer k
k = ec_get_random(group, ctx)
# R = kG
R = OpenSSL.EC_POINT_new(group)
OpenSSL.EC_POINT_mul(group, R, k, 0, 0, 0)
# Requester: 3 random blinding factors
F = OpenSSL.EC_POINT_new(group)
OpenSSL.EC_POINT_set_to_infinity(group, F)
temp = OpenSSL.EC_POINT_new(group)
Q = keypair[1]
abinv = OpenSSL.BN_new()
# F != O
while OpenSSL.EC_POINT_cmp(group, F, O, ctx) == 0:
a = ec_get_random(group, ctx)
b = ec_get_random(group, ctx)
c = ec_get_random(group, ctx)
# F = b^-1 * R...
binv = ec_invert(group, b, ctx)
OpenSSL.EC_POINT_mul(group, temp, 0, R, binv, 0)
OpenSSL.EC_POINT_copy(F, temp)
# ... + a*b^-1 * Q...
OpenSSL.BN_mul(abinv, a, binv, ctx)
OpenSSL.EC_POINT_mul(group, temp, 0, Q, abinv, 0)
OpenSSL.EC_POINT_add(group, F, F, temp, 0)
# ... + c*G
OpenSSL.EC_POINT_mul(group, temp, 0, G, c, 0)
OpenSSL.EC_POINT_add(group, F, F, temp, 0)
# F = (x0, y0)
x0 = OpenSSL.BN_new()
y0 = OpenSSL.BN_new()
OpenSSL.EC_POINT_get_affine_coordinates_GFp(group, F, x0, y0, ctx)
r = x0
# Requester: Blinding (m' = br(m) + a)
msg = os.urandom(64)
m = OpenSSL.BN_new()
OpenSSL.BN_bin2bn(msg, len(msg), m)
m_ = OpenSSL.BN_new()
OpenSSL.BN_mod_mul(m_, b, r, n, ctx)
OpenSSL.BN_mod_mul(m_, m_, m, n, ctx)
OpenSSL.BN_mod_add(m_, m_, a, n, ctx)
""" (3) Signature generation """
s_ = OpenSSL.BN_new()
OpenSSL.BN_mod_mul(s_, keypair[0], m_, n, ctx)
OpenSSL.BN_mod_add(s_, s_, k, n, ctx)
""" (4) Extraction """
s = OpenSSL.BN_new()
OpenSSL.BN_mod_mul(s, binv, s_, n, ctx)
OpenSSL.BN_mod_add(s, s, c, n, ctx)
signature = (s, F)
""" (5) Verification """
lhs = OpenSSL.EC_POINT_new(group)
rhs = OpenSSL.EC_POINT_new(group)
OpenSSL.EC_POINT_mul(group, lhs, s, 0, 0, 0)
OpenSSL.EC_POINT_mul(group, rhs, 0, Q, m, 0)
OpenSSL.EC_POINT_mul(group, rhs, 0, rhs, r, 0)
OpenSSL.EC_POINT_add(group, rhs, rhs, F, ctx)
assert OpenSSL.EC_POINT_cmp(group, lhs, rhs, ctx) == 0
print("OK!")
```

Note that nothing is being freed (as it should be) and there is no error handling, so the code shouldn't be used for production at all.

I have yet to turn this into a more usable library. This shouldn't take too long, but adding the missing functions and writing the demo was already pretty involving.

I also need to make sure that it's really working properly and that I'm doing everything right (I think I'm confusing the order `n`

with `q = 2^m`

). For now, I know that the signature passes verification with the same message, and that it expectedly fails when the message is different.

Let me know if I'm on the right track.

**Edit 1&2**: Typos.

**Edit 3**: Added ECC blind signature.

**Edit 4**: Fixed missing `ctx`

argument in declarations of `BN_mul`

and `BN_mod_mul`

. Fixed the point comparison (`F == O`

) being made with `BN_cmp`

instead of `EC_POINT_cmp`

. Made the calls to `EC_POINT_mul`

use a null `ctx`

argument.

`EC_POINT_mul`

(which was already present in `openssl.py`

) is missing the `ctx`

argument as well (it needs a sixth `ctypes.c_void_p`

argument). When added, the calls to `EC_POINT_mul`

work properly with a non-null `ctx`

. `EC_POINT_add`

doesn't need a null `ctx`

either.
`Q`

. `F`

is the point `(x0, y0)`

and `r = x0`

. The signature itself is `(s, F)`

so `r`

and `F`

are indeed shared (`r`

being part of `F`

and `F`

being part of the signature). For the blind signature itself, the requester needs `R`

from the signer, which it generates from a random `k`

for every signature. It also needs to keep that value `k`

to sign with.
`Q`

to both the requester and the verifier, as it's treated as a given. I haven't read the paper in whole, but from what I understand, the proxying with the `(k, R)`

ephemeral key is so the signer can avoid directly reusing its private key over and over again. Do you still need me to refactor the code into a more reusable library? If so, what kind of API do you want?