Request for Ring signature numerical example or simple python code

Question

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.

Answer 1

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))