4
$\begingroup$

I am reading about the Ring signature. However, I do not understand the verification process of this signature. Could you provide me a complete numerical example showing the signature creation and verification process? In case of RSA, there are many numerical example are available but I have found none for Ring Signature. I believe that It would be very helpful. enter image description here

$\endgroup$
3
  • $\begingroup$ Ring signature or Blind ring signature? $\endgroup$
    – tur11ng
    Commented Jul 29, 2022 at 22:48
  • $\begingroup$ Ring signature. Could you explain how the verification of the signature (shown in the signature) will work? How receiver can read the message even though he is not sure about the real creator of the message. $\endgroup$ Commented Jul 30, 2022 at 0:48
  • $\begingroup$ I think the reference for the particular kind of ring signature used is Ronald L. Rivest, Adi Shamir & Yael Tauman How to Leak a Secret, in proceedings of Asiacrypt 2001. It's also explained in the wiki article, with sample python code. An actual numerical example is going to be quite verbose, if detailed enough to be helpful. Perhaps the question should tell what step of the verification (in one of these two sources) is unclear. $\endgroup$
    – fgrieu
    Commented Jul 30, 2022 at 8:07

1 Answer 1

3
$\begingroup$

Let $k=\texttt{sha256}(msg)$, where $msg$ is the message we want to sign, such as the text $\texttt{"hello world!"}$.

Then define a keyed hash $H_k(input)$ as $\texttt{hmac-sha256}(k,\ input)$. The purpose of the keyed hash is to ensure that the ring signature only verifies for the specified message.

We'll start by verifying a signature, which will contain the integer $v_0$ and the public key exponents $\{e_i\}$ and corresponding moduli $\{n_i\}$ for each possible signer in the ring. The signature also lists a set of integer values $\{s_i\}$.

If the ring size is 4, we start with the specified $v_0$ value, and calculate the other $v_i$ values as follows:

$v_1 = H_k(s_1^{e_1} \oplus v_0)$
$v_2 = H_k(s_2^{e_2} \oplus v_1)$
$v_3 = H_k(s_3^{e_3} \oplus v_2)$
$v_0' = H_k(s_0^{e_0} \oplus v_3)$

The signature is valid if $v_0' \overset{?}{=}v_0$.

For brevity, I've omitted the necessary $(mod\ n_i)$ for each exponentiation. I've also simplified to standard RSA encryption. As can be seen in the python code below, extra steps are required to "Extend trap-door permutations to a common domain" as described in the How to Leak a Secret paper.

Note that each keyed hash relies on the $v_i$ value from the prior step in the ring. This means that if we tried to create such a ring with no knowledge of any private keys and without knowledge of a working $v_0$ value, we'd be stuck.

How would we have created the last row in the ring signature before knowing what the $v_3$ value would be? Knowing $v_3$ requires us to calculate $v_2$, which requires us to calculate $v_1$, which requires us to calculate $v_0$. But we can't calculate $v_0$ until we know $v_3$!

If we knew the private key $d_0$ corresponding to the public key $e_0$, we could have created the ring as follows:

Let $v_0=H_k(u)$, where $u$ is a uniformly random integer. We would choose each $s_i$ value (where $i\ge1$) as uniformly random integers, and follow the steps as described in the verification procedure above, to calculate values $v_1$, $v_2$, and eventually $v_3$.

Now, we need to somehow make it so that $v_0=H_k(u)=H_k(s_0^{e_0} \oplus v_3)$, so that our ring will verify.

This is easy. If we set $s_0=(u \oplus v_3)^{d_0}$, then $H_k(s_0^{e_0} \oplus v_3) = H_k({(u \oplus v_3)^{d_0}}^{e_0} \oplus v_3)=H_k(u \oplus v_3 \oplus v_3) = H_k(u)$.

We now have a ring signature, which could only have been created through knowledge of one of the private keys corresponding to one of the listed public keys.

I've included Python code below: (an easier-to-read version based on the Wikipedia article code)

# needs: pip install PyCryptodome
import hmac
import os
import random
import Crypto.PublicKey.RSA
from hashlib import sha256


def gen_key_pair():
    r = Crypto.PublicKey.RSA.generate(1024, os.urandom)
    return {'e': r.e, 'd': r.d, 'n': r.n}


def gen_public_key():
    r = Crypto.PublicKey.RSA.generate(1024, os.urandom)
    return {'e': r.e, 'n': r.n}


def crypto_hash(msg):
    return int(sha256(msg.encode("utf-8")).hexdigest(), 16)


def keyed_hash(key, msg):
    return int(hmac.new(bytes(str(key), 'UTF-8'), str(msg).encode("utf-8"), sha256).hexdigest(), 16)


def rsa_encrypt_or_decrypt(msg, e_or_d, n):
    q, r = divmod(msg, n)
    if ((q + 1) * n) <= (pow(2, 1024) - 1):
        result = q * n + pow(r, e_or_d, n)
    else:
        result = msg
    return result


def xor(a, b):
    return a ^ b


def sign(msg, signer_key_pair, other_public_keys):
    ring_size = len(other_public_keys) + 1
    key = crypto_hash(msg)
    u = random.randint(0, pow(2, 1023))
    v = [0] * ring_size
    v[0] = keyed_hash(key, u)

    s = [0] + [random.randint(0, pow(2, 1023)) for i in range(1, ring_size)]
    for i in range(1, ring_size):
        v[i] = keyed_hash(key, xor(v[i - 1], rsa_encrypt_or_decrypt(s[i], other_public_keys[i - 1]['e'], other_public_keys[i - 1]['n'])))
    s[0] = rsa_encrypt_or_decrypt(xor(v[ring_size - 1], u), signer_key_pair['d'], signer_key_pair['n'])

    signature = {
        'msg': msg,
        'rows':
            [{'e': signer_key_pair['e'], 'n': signer_key_pair['n'], 's': s[0]}] +
            [{'e': other_public_keys[i - 1]['e'], 'n': other_public_keys[i - 1]['n'], 's': s[i]} for i in range(1, ring_size)]
    }

    # rotate signature randomly to conceal position of true signer
    rotation = random.randint(0, ring_size - 1)
    signature['v'] = rotate(v, rotation)[ring_size - 1]
    signature['rows'] = rotate(signature['rows'], rotation)

    return signature


def rotate(list, n):
    return list[-n:] + list[:-n]


def verify(signature):
    ring_size = len(signature['rows'])
    key = crypto_hash(signature['msg'])
    v = signature['v']
    for i in range(0, ring_size):
        row = signature['rows'][i]
        v = keyed_hash(key, xor(v, rsa_encrypt_or_decrypt(row['s'], row['e'], row['n'])))
    return v == signature['v']


ring_size = 10

signer_key_pair = gen_key_pair()
other_public_keys = [gen_public_key() for i in range(ring_size - 1)]

signature = sign("hello world!", signer_key_pair, other_public_keys)
print(signature)
print("Verifies?", verify(signature))
$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.