Ring signature · Lablypedia

Related on Lably

Through Digital signature, Algorithm and Big O notation

Lab · Class 6–9Indus Valley Civilisation LabWeather Watchers Lab · Class 7–12Light & Optics Lab · Class 10Light — Reflection and Refraction — Animated Chapter Film

Ring signatures were invented by Ron Rivest, Adi Shamir, and Yael Tauman Kalai, and introduced at ASIACRYPT in 2001. The name, ring signature, comes from the ring-like structure of the signature algorithm.

Definition

Suppose that a set of entities each have public/private key pairs, (P₁, S₁), (P₂, S₂), ..., (P_n, S_n). Party i can compute a ring signature σ on a message m, on input (m, S_i, P₁, ..., P_n). Anyone can check the validity of a ring signature given σ, m, and the public keys involved, P₁, ..., P_n. If a ring signature is properly computed, it should pass the check. On the other hand, it should be hard for anyone to create a valid ring signature on any message for any set without knowing any of the private keys for that set.

4 more chapters are free with a Lably account.

Applications and modifications

In the original paper, Rivest, Shamir, and Tauman described ring signatures as a way to leak a secret. For instance, a ring signature could be used to provide an anonymous signature from "a high-ranking White House official", without revealing which official signed the message. Ring signatures are right for this application because the anonymity of a ring signature cannot be revoked, and because the group for a ring signature can be improvised.

Another application, also described in the original paper, is for deniable signatures. Here the sender and the recipient of a message form a group for the ring signature, then the signature is valid to the recipient, but anyone else will be unsure whether the recipient or the sender was the actual signer. Thus, such a signature is convincing, but cannot be transferred beyond its intended recipient.

There were various works, introducing new features and based on different assumptions:

Threshold ring signatures: Unlike standard "t-out-of-n" threshold signature, where t of n users should collaborate to sign a message, this variant of a ring signature requires t users to cooperate in the ring signing protocol. Namely, t parties S₁, ..., S_t ∈ {P₁, ..., P_n} can compute a (t, n)-ring signature, σ, on a message, m, on input (m, S₁, ..., S_t, P₁, ..., P_n).
Linkable ring signatures: The property of linkability allows one to determine whether any two signatures have been produced by the same member (under the same private key). The identity of the signer is nevertheless preserved. One of the possible applications can be an offline e-cash system.
Traceable ring signature: In addition to the previous scheme the public key of the signer is revealed (if they issue more than one signatures under the same private key). An e-voting system can be implemented using this protocol.

Efficiency

Most of the proposed algorithms have asymptotic output size $O (n)$ ; i.e., the size of the resulting signature increases linearly with the size of input (number of public keys). That means that such schemes are impracticable for real use cases with sufficiently large $n$ (for example, an e-voting with millions of participants). But for some application with relatively small median input size such estimate may be acceptable. CryptoNote implements $O (n)$ ring signature scheme by Fujisaki and Suzuki in p2p payments to achieve sender's untraceability.

More efficient algorithms have appeared recently. There are schemes with the sublinear size of the signature, as well as with constant size.

Implementation

Original scheme

The original paper describes an RSA based ring signature scheme, as well as one based on Rabin. They define a keyed "combining function" $C_{k, v} (y_{1}, y_{2}, \dots, y_{n})$ which takes a key $k$ , an initialization value $v$ , and a list of arbitrary values $y_{1}, \dots y_{n}$ . $y_{i}$ is defined as $g_{i} (x_{i})$ , where $g_{i}$ is a trap-door function (i.e. an RSA public key in the case of RSA based ring signatures).

The function $C_{k, v} (y_{1}, y_{2}, \dots, y_{n})$ is called the ring equation, and is defined below. The equation is based on a symmetric encryption function $E_{k}$ :

C_{k, v} (y_{1}, y_{2}, \dots, y_{n}) = E_{k} (y_{n} \oplus E_{k} (y_{n - 1} \oplus E_{k} (\dots \oplus E_{k} (y_{1} \oplus v) \dots)))

It outputs a single value $z$ which is forced to be equal to $v$ . The equation $v = C_{k, v} (y_{1}, y_{2}, \dots, y_{n})$ can be solved as long as at least one $y_{i}$ , and by extension $x_{i}$ , can be freely chosen. Under the assumptions of RSA, this implies knowledge of at least one of the inverses of the trap door functions $g_{i}^{- 1}$ (i.e. a private key), since $g_{i}^{- 1} (y_{i}) = x_{i}$ .

Signature generation

Generating a ring signature involves six steps. The plaintext is signified by $m$ , the ring's public keys by $P_{1}, P_{2}, \dots, P_{n}$ .

Calculate the key $k = H (m)$ , using a cryptographic hash function. This step assumes a random oracle for $H$ , since $k$ will be used as key for $E_{k}$ .
Pick a random glue value $v$ .
Pick random $x_{i}$ for all ring members but yourself ( $x_{s}$ will be calculated using the signer's private key), and calculate corresponding $y_{i} = g_{i} (x_{i})$ .
Solve the ring equation for $y_{s}$
Calculate $x_{s}$ using the signer's private key: $x_{s} = g_{s}^{- 1} (y_{s})$
The ring signature now is the $(2 n + 1)$ -tuple $(P_{1}, P_{2}, \dots, P_{n}; v; x_{1}, x_{2}, \dots, x_{n})$

Signature verification

Signature verification involves three steps.

Apply the public key trap door on all $x_{i}$ : $y_{i} = g_{i} (x_{i})$ .
Calculate the symmetric key $k = H (m)$ .
Verify that the ring equation holds $C_{k, v} (y_{1}, y_{2}, \dots, y_{n}) = v$ .

Python implementation

Here is a Python implementation of the original paper using RSA. Requires third-party module PyCryptodome.

<span id="mw1w"></span><span class="kn" id="mw2A">import</span><span class="w" id="mw2Q"> </span><span class="nn" id="mw2g">os</span> <span class="kn" id="mw2w">import</span><span class="w" id="mw3A"> </span><span class="nn" id="mw3Q">hashlib</span> <span class="kn" id="mw3g">import</span><span class="w" id="mw3w"> </span><span class="nn" id="mw4A">random</span> <span class="kn" id="mw4Q">import</span><span class="w" id="mw4g"> </span><span class="nn" id="mw4w">Crypto.PublicKey.RSA</span> <span class="kn" id="mw5A">import</span><span class="w" id="mw5Q"> </span><span class="nn" id="mw5g">functools</span> <span class="k" id="mw5w">class</span><span class="w" id="mw6A"> </span><span class="nc" id="mw6Q">Ring</span><span class="p" id="mw6g">:</span> <span class="w" id="mw6w"> </span><span class="sd" id="mw7A">"""RSA implementation."""</span> <span class="k" id="mw7Q">def</span><span class="w" id="mw7g"> </span><span class="fm" id="mw7w">__init__</span><span class="p" id="mw8A">(</span><span class="bp" id="mw8Q">self</span><span class="p" id="mw8g">,</span> <span class="n" id="mw8w">k</span><span class="p" id="mw9A">,</span> <span class="n" id="mw9Q">L</span><span class="p" id="mw9g">:</span> <span class="nb" id="mw9w">int</span> <span class="o" id="mw-A">=</span> <span class="mi" id="mw-Q">1024</span><span class="p" id="mw-g">)</span> <span class="o" id="mw-w">-></span> <span class="kc" id="mw_A">None</span><span class="p" id="mw_Q">:</span> <span class="bp" id="mw_g">self</span><span class="o" id="mw_w">.</span><span class="n" id="mwAQA">k</span> <span class="o" id="mwAQE">=</span> <span class="n" id="mwAQI">k</span> <span class="bp" id="mwAQM">self</span><span class="o" id="mwAQQ">.</span><span class="n" id="mwAQU">l</span> <span class="o" id="mwAQY">=</span> <span class="n" id="mwAQc">L</span> <span class="bp" id="mwAQg">self</span><span class="o" id="mwAQk">.</span><span class="n" id="mwAQo">n</span> <span class="o" id="mwAQs">=</span> <span class="nb" id="mwAQw">len</span><span class="p" id="mwAQ0">(</span><span class="n" id="mwAQ4">k</span><span class="p" id="mwAQ8">)</span> <span class="bp" id="mwARA">self</span><span class="o" id="mwARE">.</span><span class="n" id="mwARI">q</span> <span class="o" id="mwARM">=</span> <span class="mi" id="mwARQ">1</span> <span class="o" id="mwARU"><<</span> <span class="p" id="mwARY">(</span><span class="n" id="mwARc">L</span> <span class="o" id="mwARg">-</span> <span class="mi" id="mwARk">1</span><span class="p" id="mwARo">)</span> <span class="k" id="mwARs">def</span><span class="w" id="mwARw"> </span><span class="nf" id="mwAR0">sign_message</span><span class="p" id="mwAR4">(</span><span class="bp" id="mwAR8">self</span><span class="p" id="mwASA">,</span> <span class="n" id="mwASE">m</span><span class="p" id="mwASI">:</span> <span class="nb" id="mwASM">str</span><span class="p" id="mwASQ">,</span> <span class="n" id="mwASU">z</span><span class="p" id="mwASY">:</span> <span class="nb" id="mwASc">int</span><span class="p" id="mwASg">):</span> <span class="w" id="mwASk"> </span><span class="sd" id="mwASo">"""Sign a message."""</span> <span class="bp" id="mwASs">self</span><span class="o" id="mwASw">.</span><span class="n" id="mwAS0">_permut</span><span class="p" id="mwAS4">(</span><span class="n" id="mwAS8">m</span><span class="p" id="mwATA">)</span> <span class="n" id="mwATE">s</span> <span class="o" id="mwATI">=</span> <span class="p" id="mwATM">[</span><span class="kc" id="mwATQ">None</span><span class="p" id="mwATU">]</span> <span class="o" id="mwATY">*</span> <span class="bp" id="mwATc">self</span><span class="o" id="mwATg">.</span><span class="n" id="mwATk">n</span> <span class="n" id="mwATo">u</span> <span class="o" id="mwATs">=</span> <span class="n" id="mwATw">random</span><span class="o" id="mwAT0">.</span><span class="n" id="mwAT4">randint</span><span class="p" id="mwAT8">(</span><span class="mi" id="mwAUA">0</span><span class="p" id="mwAUE">,</span> <span class="bp" id="mwAUI">self</span><span class="o" id="mwAUM">.</span><span class="n" id="mwAUQ">q</span><span class="p" id="mwAUU">)</span> <span class="n" id="mwAUY">c</span> <span class="o" id="mwAUc">=</span> <span class="n" id="mwAUg">v</span> <span class="o" id="mwAUk">=</span> <span class="bp" id="mwAUo">self</span><span class="o" id="mwAUs">.</span><span class="n" id="mwAUw">_E</span><span class="p" id="mwAU0">(</span><span class="n" id="mwAU4">u</span><span class="p" id="mwAU8">)</span> <span class="n" id="mwAVA">first_range</span> <span class="o" id="mwAVE">=</span> <span class="nb" id="mwAVI">list</span><span class="p" id="mwAVM">(</span><span class="nb" id="mwAVQ">range</span><span class="p" id="mwAVU">(</span><span class="n" id="mwAVY">z</span> <span class="o" id="mwAVc">+</span> <span class="mi" id="mwAVg">1</span><span class="p" id="mwAVk">,</span> <span class="bp" id="mwAVo">self</span><span class="o" id="mwAVs">.</span><span class="n" id="mwAVw">n</span><span class="p" id="mwAV0">))</span> <span class="n" id="mwAV4">second_range</span> <span class="o" id="mwAV8">=</span> <span class="nb" id="mwAWA">list</span><span class="p" id="mwAWE">(</span><span class="nb" id="mwAWI">range</span><span class="p" id="mwAWM">(</span><span class="n" id="mwAWQ">z</span><span class="p" id="mwAWU">))</span> <span class="n" id="mwAWY">whole_range</span> <span class="o" id="mwAWc">=</span> <span class="n" id="mwAWg">first_range</span> <span class="o" id="mwAWk">+</span> <span class="n" id="mwAWo">second_range</span> <span class="k" id="mwAWs">for</span> <span class="n" id="mwAWw">i</span> <span class="ow" id="mwAW0">in</span> <span class="n" id="mwAW4">whole_range</span><span class="p" id="mwAW8">:</span> <span class="n" id="mwAXA">s</span><span class="p" id="mwAXE">[</span><span class="n" id="mwAXI">i</span><span class="p" id="mwAXM">]</span> <span class="o" id="mwAXQ">=</span> <span class="n" id="mwAXU">random</span><span class="o" id="mwAXY">.</span><span class="n" id="mwAXc">randint</span><span class="p" id="mwAXg">(</span><span class="mi" id="mwAXk">0</span><span class="p" id="mwAXo">,</span> <span class="bp" id="mwAXs">self</span><span class="o" id="mwAXw">.</span><span class="n" id="mwAX0">q</span><span class="p" id="mwAX4">)</span> <span class="n" id="mwAX8">e</span> <span class="o" id="mwAYA">=</span> <span class="bp" id="mwAYE">self</span><span class="o" id="mwAYI">.</span><span class="n" id="mwAYM">_g</span><span class="p" id="mwAYQ">(</span><span class="n" id="mwAYU">s</span><span class="p" id="mwAYY">[</span><span class="n" id="mwAYc">i</span><span class="p" id="mwAYg">],</span> <span class="bp" id="mwAYk">self</span><span class="o" id="mwAYo">.</span><span class="n" id="mwAYs">k</span><span class="p" id="mwAYw">[</span><span class="n" id="mwAY0">i</span><span class="p" id="mwAY4">]</span><span class="o" id="mwAY8">.</span><span class="n" id="mwAZA">e</span><span class="p" id="mwAZE">,</span> <span class="bp" id="mwAZI">self</span><span class="o" id="mwAZM">.</span><span class="n" id="mwAZQ">k</span><span class="p" id="mwAZU">[</span><span class="n" id="mwAZY">i</span><span class="p" id="mwAZc">]</span><span class="o" id="mwAZg">.</span><span class="n" id="mwAZk">n</span><span class="p" id="mwAZo">)</span> <span class="n" id="mwAZs">v</span> <span class="o" id="mwAZw">=</span> <span class="bp" id="mwAZ0">self</span><span class="o" id="mwAZ4">.</span><span class="n" id="mwAZ8">_E</span><span class="p" id="mwAaA">(</span><span class="n" id="mwAaE">v</span> <span class="o" id="mwAaI">^</span> <span class="n" id="mwAaM">e</span><span class="p" id="mwAaQ">)</span> <span class="k" id="mwAaU">if</span> <span class="p" id="mwAaY">(</span><span class="n" id="mwAac">i</span> <span class="o" id="mwAag">+</span> <span class="mi" id="mwAak">1</span><span class="p" id="mwAao">)</span> <span class="o" id="mwAas">%</span> <span class="bp" id="mwAaw">self</span><span class="o" id="mwAa0">.</span><span class="n" id="mwAa4">n</span> <span class="o" id="mwAa8">==</span> <span class="mi" id="mwAbA">0</span><span class="p" id="mwAbE">:</span> <span class="n" id="mwAbI">c</span> <span class="o" id="mwAbM">=</span> <span class="n" id="mwAbQ">v</span> <span class="n" id="mwAbU">s</span><span class="p" id="mwAbY">[</span><span class="n" id="mwAbc">z</span><span class="p" id="mwAbg">]</span> <span class="o" id="mwAbk">=</span> <span class="bp" id="mwAbo">self</span><span class="o" id="mwAbs">.</span><span class="n" id="mwAbw">_g</span><span class="p" id="mwAb0">(</span><span class="n" id="mwAb4">v</span> <span class="o" id="mwAb8">^</span> <span class="n" id="mwAcA">u</span><span class="p" id="mwAcE">,</span> <span class="bp" id="mwAcI">self</span><span class="o" id="mwAcM">.</span><span class="n" id="mwAcQ">k</span><span class="p" id="mwAcU">[</span><span class="n" id="mwAcY">z</span><span class="p" id="mwAcc">]</span><span class="o" id="mwAcg">.</span><span class="n" id="mwAck">d</span><span class="p" id="mwAco">,</span> <span class="bp" id="mwAcs">self</span><span class="o" id="mwAcw">.</span><span class="n" id="mwAc0">k</span><span class="p" id="mwAc4">[</span><span class="n" id="mwAc8">z</span><span class="p" id="mwAdA">]</span><span class="o" id="mwAdE">.</span><span class="n" id="mwAdI">n</span><span class="p" id="mwAdM">)</span> <span class="k" id="mwAdQ">return</span> <span class="p" id="mwAdU">[</span><span class="n" id="mwAdY">c</span><span class="p" id="mwAdc">]</span> <span class="o" id="mwAdg">+</span> <span class="n" id="mwAdk">s</span> <span class="k" id="mwAdo">def</span><span class="w" id="mwAds"> </span><span class="nf" id="mwAdw">verify_message</span><span class="p" id="mwAd0">(</span><span class="bp" id="mwAd4">self</span><span class="p" id="mwAd8">,</span> <span class="n" id="mwAeA">m</span><span class="p" id="mwAeE">:</span> <span class="nb" id="mwAeI">str</span><span class="p" id="mwAeM">,</span> <span class="n" id="mwAeQ">X</span><span class="p" id="mwAeU">)</span> <span class="o" id="mwAeY">-></span> <span class="nb" id="mwAec">bool</span><span class="p" id="mwAeg">:</span> <span class="w" id="mwAek"> </span><span class="sd" id="mwAeo">"""Verify a message."""</span> <span class="bp" id="mwAes">self</span><span class="o" id="mwAew">.</span><span class="n" id="mwAe0">_permut</span><span class="p" id="mwAe4">(</span><span class="n" id="mwAe8">m</span><span class="p" id="mwAfA">)</span> <span class="k" id="mwAfE">def</span><span class="w" id="mwAfI"> </span><span class="nf" id="mwAfM">_f</span><span class="p" id="mwAfQ">(</span><span class="n" id="mwAfU">i</span><span class="p" id="mwAfY">):</span> <span class="k" id="mwAfc">return</span> <span class="bp" id="mwAfg">self</span><span class="o" id="mwAfk">.</span><span class="n" id="mwAfo">_g</span><span class="p" id="mwAfs">(</span><span class="n" id="mwAfw">X</span><span class="p" id="mwAf0">[</span><span class="n" id="mwAf4">i</span> <span class="o" id="mwAf8">+</span> <span class="mi" id="mwAgA">1</span><span class="p" id="mwAgE">],</span> <span class="bp" id="mwAgI">self</span><span class="o" id="mwAgM">.</span><span class="n" id="mwAgQ">k</span><span class="p" id="mwAgU">[</span><span class="n" id="mwAgY">i</span><span class="p" id="mwAgc">]</span><span class="o" id="mwAgg">.</span><span class="n" id="mwAgk">e</span><span class="p" id="mwAgo">,</span> <span class="bp" id="mwAgs">self</span><span class="o" id="mwAgw">.</span><span class="n" id="mwAg0">k</span><span class="p" id="mwAg4">[</span><span class="n" id="mwAg8">i</span><span class="p" id="mwAhA">]</span><span class="o" id="mwAhE">.</span><span class="n" id="mwAhI">n</span><span class="p" id="mwAhM">)</span> <span class="n" id="mwAhQ">y</span> <span class="o" id="mwAhU">=</span> <span class="nb" id="mwAhY">map</span><span class="p" id="mwAhc">(</span><span class="n" id="mwAhg">_f</span><span class="p" id="mwAhk">,</span> <span class="nb" id="mwAho">range</span><span class="p" id="mwAhs">(</span><span class="nb" id="mwAhw">len</span><span class="p" id="mwAh0">(</span><span class="n" id="mwAh4">X</span><span class="p" id="mwAh8">)</span> <span class="o" id="mwAiA">-</span> <span class="mi" id="mwAiE">1</span><span class="p" id="mwAiI">))</span> <span class="n" id="mwAiM">y</span> <span class="o" id="mwAiQ">=</span> <span class="nb" id="mwAiU">list</span><span class="p" id="mwAiY">(</span><span class="n" id="mwAic">y</span><span class="p" id="mwAig">)</span> <span class="k" id="mwAik">def</span><span class="w" id="mwAio"> </span><span class="nf" id="mwAis">_g</span><span class="p" id="mwAiw">(</span><span class="n" id="mwAi0">x</span><span class="p" id="mwAi4">,</span> <span class="n" id="mwAi8">i</span><span class="p" id="mwAjA">):</span> <span class="k" id="mwAjE">return</span> <span class="bp" id="mwAjI">self</span><span class="o" id="mwAjM">.</span><span class="n" id="mwAjQ">_E</span><span class="p" id="mwAjU">(</span><span class="n" id="mwAjY">x</span> <span class="o" id="mwAjc">^</span> <span class="n" id="mwAjg">y</span><span class="p" id="mwAjk">[</span><span class="n" id="mwAjo">i</span><span class="p" id="mwAjs">])</span> <span class="n" id="mwAjw">r</span> <span class="o" id="mwAj0">=</span> <span class="n" id="mwAj4">functools</span><span class="o" id="mwAj8">.</span><span class="n" id="mwAkA">reduce</span><span class="p" id="mwAkE">(</span><span class="n" id="mwAkI">_g</span><span class="p" id="mwAkM">,</span> <span class="nb" id="mwAkQ">range</span><span class="p" id="mwAkU">(</span><span class="bp" id="mwAkY">self</span><span class="o" id="mwAkc">.</span><span class="n" id="mwAkg">n</span><span class="p" id="mwAkk">),</span> <span class="n" id="mwAko">X</span><span class="p" id="mwAks">[</span><span class="mi" id="mwAkw">0</span><span class="p" id="mwAk0">])</span> <span class="k" id="mwAk4">return</span> <span class="n" id="mwAk8">r</span> <span class="o" id="mwAlA">==</span> <span class="n" id="mwAlE">X</span><span class="p" id="mwAlI">[</span><span class="mi" id="mwAlM">0</span><span class="p" id="mwAlQ">]</span> <span class="k" id="mwAlU">def</span><span class="w" id="mwAlY"> </span><span class="nf" id="mwAlc">_permut</span><span class="p" id="mwAlg">(</span><span class="bp" id="mwAlk">self</span><span class="p" id="mwAlo">,</span> <span class="n" id="mwAls">m</span><span class="p" id="mwAlw">):</span> <span class="n" id="mwAl0">msg</span> <span class="o" id="mwAl4">=</span> <span class="n" id="mwAl8">m</span><span class="o" id="mwAmA">.</span><span class="n" id="mwAmE">encode</span><span class="p" id="mwAmI">(</span><span class="s2" id="mwAmM">"utf-8"</span><span class="p" id="mwAmQ">)</span> <span class="bp" id="mwAmU">self</span><span class="o" id="mwAmY">.</span><span class="n" id="mwAmc">p</span> <span class="o" id="mwAmg">=</span> <span class="nb" id="mwAmk">int</span><span class="p" id="mwAmo">(</span><span class="n" id="mwAms">hashlib</span><span class="o" id="mwAmw">.</span><span class="n" id="mwAm0">sha1</span><span class="p" id="mwAm4">(</span><span class="n" id="mwAm8">msg</span><span class="p" id="mwAnA">)</span><span class="o" id="mwAnE">.</span><span class="n" id="mwAnI">hexdigest</span><span class="p" id="mwAnM">(),</span> <span class="mi" id="mwAnQ">16</span><span class="p" id="mwAnU">)</span> <span class="k" id="mwAnY">def</span><span class="w" id="mwAnc"> </span><span class="nf" id="mwAng">_E</span><span class="p" id="mwAnk">(</span><span class="bp" id="mwAno">self</span><span class="p" id="mwAns">,</span> <span class="n" id="mwAnw">x</span><span class="p" id="mwAn0">):</span> <span class="n" id="mwAn4">msg</span> <span class="o" id="mwAn8">=</span> <span class="sa" id="mwAoA">f</span><span class="s2" id="mwAoE">"</span><span class="si" id="mwAoI">{</span><span class="n" id="mwAoM">x</span><span class="si" id="mwAoQ">}{</span><span class="bp" id="mwAoU">self</span><span class="o" id="mwAoY">.</span><span class="n" id="mwAoc">p</span><span class="si" id="mwAog">}</span><span class="s2" id="mwAok">"</span><span class="o" id="mwAoo">.</span><span class="n" id="mwAos">encode</span><span class="p" id="mwAow">(</span><span class="s2" id="mwAo0">"utf-8"</span><span class="p" id="mwAo4">)</span> <span class="k" id="mwAo8">return</span> <span class="nb" id="mwApA">int</span><span class="p" id="mwApE">(</span><span class="n" id="mwApI">hashlib</span><span class="o" id="mwApM">.</span><span class="n" id="mwApQ">sha1</span><span class="p" id="mwApU">(</span><span class="n" id="mwApY">msg</span><span class="p" id="mwApc">)</span><span class="o" id="mwApg">.</span><span class="n" id="mwApk">hexdigest</span><span class="p" id="mwApo">(),</span> <span class="mi" id="mwAps">16</span><span class="p" id="mwApw">)</span> <span class="k" id="mwAp0">def</span><span class="w" id="mwAp4"> </span><span class="nf" id="mwAp8">_g</span><span class="p" id="mwAqA">(</span><span class="bp" id="mwAqE">self</span><span class="p" id="mwAqI">,</span> <span class="n" id="mwAqM">x</span><span class="p" id="mwAqQ">,</span> <span class="n" id="mwAqU">e</span><span class="p" id="mwAqY">,</span> <span class="n" id="mwAqc">n</span><span class="p" id="mwAqg">):</span> <span class="n" id="mwAqk">q</span><span class="p" id="mwAqo">,</span> <span class="n" id="mwAqs">r</span> <span class="o" id="mwAqw">=</span> <span class="nb" id="mwAq0">divmod</span><span class="p" id="mwAq4">(</span><span class="n" id="mwAq8">x</span><span class="p" id="mwArA">,</span> <span class="n" id="mwArE">n</span><span class="p" id="mwArI">)</span> <span class="k" id="mwArM">if</span> <span class="p" id="mwArQ">((</span><span class="n" id="mwArU">q</span> <span class="o" id="mwArY">+</span> <span class="mi" id="mwArc">1</span><span class="p" id="mwArg">)</span> <span class="o" id="mwArk">*</span> <span class="n" id="mwAro">n</span><span class="p" id="mwArs">)</span> <span class="o" id="mwArw"><=</span> <span class="p" id="mwAr0">((</span><span class="mi" id="mwAr4">1</span> <span class="o" id="mwAr8"><<</span> <span class="bp" id="mwAsA">self</span><span class="o" id="mwAsE">.</span><span class="n" id="mwAsI">l</span><span class="p" id="mwAsM">)</span> <span class="o" id="mwAsQ">-</span> <span class="mi" id="mwAsU">1</span><span class="p" id="mwAsY">):</span> <span class="n" id="mwAsc">result</span> <span class="o" id="mwAsg">=</span> <span class="n" id="mwAsk">q</span> <span class="o" id="mwAso">*</span> <span class="n" id="mwAss">n</span> <span class="o" id="mwAsw">+</span> <span class="nb" id="mwAs0">pow</span><span class="p" id="mwAs4">(</span><span class="n" id="mwAs8">r</span><span class="p" id="mwAtA">,</span> <span class="n" id="mwAtE">e</span><span class="p" id="mwAtI">,</span> <span class="n" id="mwAtM">n</span><span class="p" id="mwAtQ">)</span> <span class="k" id="mwAtU">else</span><span class="p" id="mwAtY">:</span> <span class="n" id="mwAtc">result</span> <span class="o" id="mwAtg">=</span> <span class="n" id="mwAtk">x</span> <span class="k" id="mwAto">return</span> <span class="n" id="mwAts">result</span>

To sign and verify 2 messages in a ring of 4 users:

<span id="mwAt8"></span><span class="n" id="mwAuA">size</span> <span class="o" id="mwAuE">=</span> <span class="mi" id="mwAuI">4</span> <span class="n" id="mwAuM">msg1</span><span class="p" id="mwAuQ">,</span> <span class="n" id="mwAuU">msg2</span> <span class="o" id="mwAuY">=</span> <span class="s2" id="mwAuc">"hello"</span><span class="p" id="mwAug">,</span> <span class="s2" id="mwAuk">"world!"</span> <span class="k" id="mwAuo">def</span><span class="w" id="mwAus"> </span><span class="nf" id="mwAuw">_rn</span><span class="p" id="mwAu0">(</span><span class="n" id="mwAu4">_</span><span class="p" id="mwAu8">):</span> <span class="k" id="mwAvA">return</span> <span class="n" id="mwAvE">Crypto</span><span class="o" id="mwAvI">.</span><span class="n" id="mwAvM">PublicKey</span><span class="o" id="mwAvQ">.</span><span class="n" id="mwAvU">RSA</span><span class="o" id="mwAvY">.</span><span class="n" id="mwAvc">generate</span><span class="p" id="mwAvg">(</span><span class="mi" id="mwAvk">1024</span><span class="p" id="mwAvo">,</span> <span class="n" id="mwAvs">os</span><span class="o" id="mwAvw">.</span><span class="n" id="mwAv0">urandom</span><span class="p" id="mwAv4">)</span> <span class="n" id="mwAv8">key</span> <span class="o" id="mwAwA">=</span> <span class="nb" id="mwAwE">map</span><span class="p" id="mwAwI">(</span><span class="n" id="mwAwM">_rn</span><span class="p" id="mwAwQ">,</span> <span class="nb" id="mwAwU">range</span><span class="p" id="mwAwY">(</span><span class="n" id="mwAwc">size</span><span class="p" id="mwAwg">))</span> <span class="n" id="mwAwk">key</span> <span class="o" id="mwAwo">=</span> <span class="nb" id="mwAws">list</span><span class="p" id="mwAww">(</span><span class="n" id="mwAw0">key</span><span class="p" id="mwAw4">)</span> <span class="n" id="mwAw8">r</span> <span class="o" id="mwAxA">=</span> <span class="n" id="mwAxE">Ring</span><span class="p" id="mwAxI">(</span><span class="n" id="mwAxM">key</span><span class="p" id="mwAxQ">)</span> <span class="k" id="mwAxU">for</span> <span class="n" id="mwAxY">i</span> <span class="ow" id="mwAxc">in</span> <span class="nb" id="mwAxg">range</span><span class="p" id="mwAxk">(</span><span class="n" id="mwAxo">size</span><span class="p" id="mwAxs">):</span> <span class="n" id="mwAxw">signature_1</span> <span class="o" id="mwAx0">=</span> <span class="n" id="mwAx4">r</span><span class="o" id="mwAx8">.</span><span class="n" id="mwAyA">sign_message</span><span class="p" id="mwAyE">(</span><span class="n" id="mwAyI">msg1</span><span class="p" id="mwAyM">,</span> <span class="n" id="mwAyQ">i</span><span class="p" id="mwAyU">)</span> <span class="n" id="mwAyY">signature_2</span> <span class="o" id="mwAyc">=</span> <span class="n" id="mwAyg">r</span><span class="o" id="mwAyk">.</span><span class="n" id="mwAyo">sign_message</span><span class="p" id="mwAys">(</span><span class="n" id="mwAyw">msg2</span><span class="p" id="mwAy0">,</span> <span class="n" id="mwAy4">i</span><span class="p" id="mwAy8">)</span> <span class="k" id="mwAzA">assert</span> <span class="n" id="mwAzE">r</span><span class="o" id="mwAzI">.</span><span class="n" id="mwAzM">verify_message</span><span class="p" id="mwAzQ">(</span><span class="n" id="mwAzU">msg1</span><span class="p" id="mwAzY">,</span> <span class="n" id="mwAzc">signature_1</span><span class="p" id="mwAzg">)</span> <span class="ow" id="mwAzk">and</span> <span class="n" id="mwAzo">r</span><span class="o" id="mwAzs">.</span><span class="n" id="mwAzw">verify_message</span><span class="p" id="mwAz0">(</span><span class="n" id="mwAz4">msg2</span><span class="p" id="mwAz8">,</span> <span class="n" id="mwA0A">signature_2</span><span class="p" id="mwA0E">)</span> <span class="ow" id="mwA0I">and</span> <span class="ow" id="mwA0M">not</span> <span class="n" id="mwA0Q">r</span><span class="o" id="mwA0U">.</span><span class="n" id="mwA0Y">verify_message</span><span class="p" id="mwA0c">(</span><span class="n" id="mwA0g">msg1</span><span class="p" id="mwA0k">,</span> <span class="n" id="mwA0o">signature_2</span><span class="p" id="mwA0s">)</span>

Cryptocurrencies

Monero and several other cryptocurrencies use this technology.

More in Computing and communication

ISBNUnique numeric book identifier since 1970 X (social network)American social networking service Wayback MachineDigital archive by the Internet Archive Python (programming language)General-purpose programming language MacOSOperating system for Apple computers UnicodeCharacter encoding standard