Кольцевая подпись

В криптографии кольцевая подпись — это тип цифровой подписи , которую может выполнить любой член группы пользователей, у каждого из которых есть ключи . Таким образом, сообщение, подписанное кольцевой подписью, одобрено кем-то из определенной группы людей. Одним из свойств безопасности кольцевой подписи является то, что с вычислительной точки зрения невозможно определить, какой из ключей членов набора использовался для создания подписи. Кольцевые подписи похожи на групповые подписи , но отличаются двумя ключевыми моментами: во-первых, невозможно отменить анонимность отдельной подписи; и, во-вторых, любой набор пользователей может использоваться в качестве набора для подписи без дополнительной настройки.

Кольцевые подписи были изобретены Роном Ривестом , Ади Шамиром и Яэлем Тауманом Калаем и представлены на ASIACRYPT в 2001 году. ^{[ 1 ]} Название «кольцевая подпись » происходит от кольцевой структуры алгоритма подписи .

Определение

Предположим, что каждый из множества объектов имеет пары открытого/закрытого ключей ( P ₁ , S ₁ ), ( P ₂ , S ₂ ), ..., ( P _n , S _n ). Сторона i сообщении m на входе ( m , Si _, n P ₁ , ..., P _{может вычислить кольцевую подпись σ на} ). Любой может проверить достоверность кольцевой подписи, зная σ, m и задействованные открытые ключи P ₁ , ..., P _n . Если кольцевая подпись рассчитана правильно, она должна пройти проверку. С другой стороны, кому-либо будет сложно создать действительную кольцевую подпись для любого сообщения для любого набора, не зная каких-либо закрытых ключей для этого набора. ^{[ 2 ]}

Приложения и модификации

Поведение схемы кольцевой подписи Ривеста, Шамира и Таумана

В оригинальной статье Ривест, Шамир и Тауман описали кольцевые подписи как способ раскрытия секрета. Например, кольцевая подпись может использоваться для обеспечения анонимной подписи «высокопоставленного чиновника Белого дома », не раскрывая, какой чиновник подписал сообщение. Кольцевые подписи подходят для этого приложения, поскольку анонимность кольцевой подписи не может быть отозвана, а также потому, что группу для кольцевой подписи можно создать импровизировать.

Другое применение, также описанное в оригинальной статье, предназначено для отрицаемых подписей . Здесь отправитель и получатель сообщения образуют группу для кольцевой подписи, тогда подпись действительна для получателя, но кто-либо еще не будет уверен, был ли фактический подписавший получатель или отправитель. Таким образом, такая подпись убедительна, но не может быть передана за пределы предполагаемого получателя.

Были различные работы, вводившие новые возможности и основанные на разных предположениях:

Пороговые кольцевые сигнатуры: ^{[ 3 ]} В отличие от стандартной « t -out-of- n » пороговой подписи , где для подписания сообщения должны сотрудничать t из n пользователей, этот вариант кольцевой подписи требует t сотрудничества пользователей в протоколе кольцевой подписи . А именно, t сторон S ₁ , ..., S _t ∈ { P ₁ , ..., P _n } могут вычислить ( t , n )-кольцевую подпись σ в сообщении m на входе ( m , С ₁ , ..., Ст _т , П ₁ , ..., П _н ).
Связываемые кольцевые подписи: ^{[ 4 ]} Свойство связываемости позволяет определить, были ли какие-либо две подписи созданы одним и тем же участником (под одним и тем же закрытым ключом). Тем не менее личность подписавшего сохраняется. Одним из возможных приложений может стать автономная система электронных денег .
Отслеживаемая кольцевая подпись: ^{[ 5 ]} В дополнение к предыдущей схеме раскрывается открытый ключ подписывающего лица (если под одним и тем же закрытым ключом выдается более одной подписи). систему электронного голосования . С использованием этого протокола можно реализовать

Эффективность

Большинство предложенных алгоритмов имеют асимптотический размер вывода. $O(n)$ ; т. е. размер результирующей подписи увеличивается линейно с размером входных данных (количество открытых ключей). Это означает, что такие схемы неосуществимы для реальных случаев использования с достаточно большими $n$ (например, электронное голосование с миллионами участников). Но для некоторых приложений с относительно небольшим медианным размером входных данных такая оценка может быть приемлемой. CryptoNote реализует $O(n)$ Схема кольцевой подписи Фудзисаки и Сузуки ^{[ 5 ]} в p2p-платежах для обеспечения невозможности отслеживания отправителя.

Недавно появились более эффективные алгоритмы. Есть схемы с сублинейным размером подписи, ^{[ 6 ]} так и с постоянным размером. ^{[ 7 ]}

Выполнение

Оригинальная схема

В оригинальной статье описывается схема кольцевой подписи на основе RSA , а также схема, основанная на подписях Рабина . Они определяют ключевую «функцию объединения». $C_{k,v}(y_{1},y_{2},\dots ,y_{n})$ который принимает ключ $k$ , значение инициализации $v$ и список произвольных значений $y_{1},\dots y_{n}$ . $y_{i}$ определяется как $g_{i}(x_{i})$ , где $g_{i}$ является функцией-ловушкой (т.е. открытым ключом RSA в случае кольцевых подписей на основе RSA).

Функция $C_{k,v}(y_{1},y_{2},\dots ,y_{n})$ называется кольцевым уравнением и определяется ниже. Уравнение основано на симметричной функции шифрования $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 )))

Он выводит одно значение $z$ который вынужден быть равен $v$ . Уравнение $v=C_{k,v}(y_{1},y_{2},\dots ,y_{n})$ можно решить, если есть хотя бы одно $y_{i}$ и, соответственно, $x_{i}$ , может быть выбран свободно. В предположениях RSA это подразумевает знание хотя бы одной из обратных функций люка. $g_{i}^{-1}$ (т.е. закрытый ключ), поскольку $g_{i}^{-1}(y_{i})=x_{i}$ .

Генерация подписи

Создание кольцевой подписи включает шесть шагов. Открытый текст обозначается $m$ , открытые ключи кольца $P_{1},P_{2},\dots ,P_{n}$ .

Рассчитать ключ $k={\mathcal {H}}(m)$ , используя криптографическую хэш-функцию . На этом этапе предполагается случайный оракул для ${\mathcal {H}}$ , с $k$ будет использоваться в качестве ключа для $E_{k}$ .
Выберите случайное значение клея $v$ .
Выбрать случайно $x_{i}$ для всех участников кольца, кроме вас ( $x_{s}$ будет рассчитываться с использованием закрытого ключа подписывающей стороны) и вычислять соответствующий $y_{i}=g_{i}(x_{i})$ .
Решите кольцевое уравнение для $y_{s}$
Рассчитать $x_{s}$ используя закрытый ключ подписывающего лица: $x_{s}=g_{s}^{-1}(y_{s})$
Кольцевая подпись теперь $(2n+1)$ -кортеж $(P_{1},P_{2},\dots ,P_{n};v;x_{1},x_{2},\dots ,x_{n})$

Проверка подписи

Проверка подписи включает в себя три этапа.

Примените люк с открытым ключом ко всем $x_{i}$ : $y_{i}=g_{i}(x_{i})$ .
Вычислить симметричный ключ $k={\mathcal {H}}(m)$ .
Убедитесь, что кольцевое уравнение выполнено $C_{k,v}(y_{1},y_{2},\dots ,y_{n})=v$ .

Реализация Python

Вот на Python реализация оригинальной статьи с использованием RSA . Требуется сторонний модуль PyCryptodome.

import os
import hashlib
import random
import Crypto.PublicKey.RSA

import functools

class Ring:
    """RSA implementation."""

    def __init__(self, k, L: int = 1024) -> None:
        self.k = k
        self.l = L
        self.n = len(k)
        self.q = 1 << (L - 1)

    def sign_message(self, m: str, z: int):
        self._permut(m)
        s = [None] * self.n
        u = random.randint(0, self.q)
        c = v = self._E(u)

        first_range = list(range(z + 1, self.n))
        second_range = list(range(z))
        whole_range = first_range + second_range

        for i in whole_range:
            s[i] = random.randint(0, self.q)
            e = self._g(s[i], self.k[i].e, self.k[i].n)
            v = self._E(v ^ e)
            if (i + 1) % self.n == 0:
                c = v

        s[z] = self._g(v ^ u, self.k[z].d, self.k[z].n)
        return [c] + s

    def verify_message(self, m: str, X) -> bool:
        self._permut(m)

        def _f(i):
            return self._g(X[i + 1], self.k[i].e, self.k[i].n)

        y = map(_f, range(len(X) - 1))
        y = list(y)

        def _g(x, i):
            return self._E(x ^ y[i])

        r = functools.reduce(_g, range(self.n), X[0])
        return r == X[0]

    def _permut(self, m):
        msg = m.encode("utf-8")
        self.p = int(hashlib.sha1(msg).hexdigest(), 16)

    def _E(self, x):
        msg = f"{x}{self.p}".encode("utf-8")
        return int(hashlib.sha1(msg).hexdigest(), 16)

    def _g(self, x, e, n):
        q, r = divmod(x, n)
        if ((q + 1) * n) <= ((1 << self.l) - 1):
            result = q * n + pow(r, e, n)
        else:
            result = x
        return result

Чтобы подписать и подтвердить 2 сообщения в кольце из 4 пользователей:

size = 4
msg1, msg2 = "hello", "world!"

def _rn(_):
    return Crypto.PublicKey.RSA.generate(1024, os.urandom)

key = map(_rn, range(size))
key = list(key)

r = Ring(key)

for i in range(size):
    signature_1 = r.sign_message(msg1, i)
    signature_2 = r.sign_message(msg2, i)
    assert r.verify_message(msg1, signature_1) and r.verify_message(msg2, signature_2) and not r.verify_message(msg1, signature_2)

Криптовалюты

Monero и несколько других криптовалют используют эту технологию. ^{[ нужна ссылка ]}

См. также

Свидетель-неотличимые доказательства

Ссылки

В эту статью включен текст , доступный по лицензии CC BY-SA 4.0 .

^ Ривест, Рональд Л .; Шамир, Ади ; Тауман, Яэль (2001). «Как раскрыть секрет» . Достижения в криптологии — ASIACRYPT 2001 . Конспекты лекций по информатике. Том. 2248. стр. 552–565. дои : 10.1007/3-540-45682-1_32 . ISBN 978-3-540-42987-6 .
^ Дебнат, Ашмита; Сингаравелу, Прадхипкумар; Верма, Шекхар (19 декабря 2012 г.). «Эффективная схема сохранения пространственной конфиденциальности для сенсорной сети» . Центральноевропейский инженерный журнал . 3 (1): 1–10. дои : 10.2478/s13531-012-0048-7 . S2CID 137248994 .
^ Э. Брессон; Дж. Стерн; М. Шидло (2002). «Пороговые кольцевые подписи и приложения для специальных групп» (PDF) . Достижения криптологии — КРИПТО 2002 . Конспекты лекций по информатике. Том. 2442. стр. 465–480. дои : 10.1007/3-540-45708-9_30 . ISBN 978-3-540-44050-5 .
^ Лю, Джозеф К.; Вонг, Дункан С. (2005). «Связываемые кольцевые подписи: модели безопасности и новые схемы». Вычислительная наука и ее приложения – ICCSA 2005 . Конспекты лекций по информатике. Том. 2. стр. 614–623. дои : 10.1007/11424826_65 . ISBN 978-3-540-25861-2 . {{cite book}}: |journal= игнорируется ( помогите )
^ Перейти обратно: ^а ^б Фудзисаки, Эйитиро; Сузуки, Котаро (2007). «Прослеживаемая кольцевая подпись». Криптография с открытым ключом : 181–200.
^ Фудзисаки, Эйитиро (2011). «Прослеживаемые кольцевые подписи сублинейного размера без случайных оракулов». IEICE Transactions по основам электроники, связи и информатики . 95 (1): 393–415. Бибкод : 2012IEITF..95..151F . doi : 10.1587/transfun.E95.A.151 .
^ Ау, Ман Хо; Лю, Джозеф К.; Сусило, Вилли; Юэнь, Цз Хон (2006). «Кольцевая подпись постоянного размера на основе идентификатора и отзывная кольцевая подпись, связанная с iff-связкой». Прогресс в криптологии - INDOCRYPT 2006 . Конспекты лекций по информатике. Том. 4329. стр. 364–378. дои : 10.1007/11941378_26 . ISBN 978-3-540-49767-7 .

[1] Ривест, Рональд Л .; Шамир, Ади ; Тауман, Яэль (2001). «Как раскрыть секрет» . Достижения в криптологии — ASIACRYPT 2001 . Конспекты лекций по информатике. Том. 2248. стр. 552–565. дои : 10.1007/3-540-45682-1_32 . ISBN 978-3-540-42987-6 .

[2] Дебнат, Ашмита; Сингаравелу, Прадхипкумар; Верма, Шекхар (19 декабря 2012 г.). «Эффективная схема сохранения пространственной конфиденциальности для сенсорной сети» . Центральноевропейский инженерный журнал . 3 (1): 1–10. дои : 10.2478/s13531-012-0048-7 . S2CID 137248994 .

[3] Э. Брессон; Дж. Стерн; М. Шидло (2002). «Пороговые кольцевые подписи и приложения для специальных групп» (PDF) . Достижения криптологии — КРИПТО 2002 . Конспекты лекций по информатике. Том. 2442. стр. 465–480. дои : 10.1007/3-540-45708-9_30 . ISBN 978-3-540-44050-5 .

[4] Лю, Джозеф К.; Вонг, Дункан С. (2005). «Связываемые кольцевые подписи: модели безопасности и новые схемы». Вычислительная наука и ее приложения – ICCSA 2005 . Конспекты лекций по информатике. Том. 2. стр. 614–623. дои : 10.1007/11424826_65 . ISBN 978-3-540-25861-2 . {{cite book}}: |journal= игнорируется ( помогите )

[FS07-5] Перейти обратно: ^а ^б Фудзисаки, Эйитиро; Сузуки, Котаро (2007). «Прослеживаемая кольцевая подпись». Криптография с открытым ключом : 181–200.

[6] Фудзисаки, Эйитиро (2011). «Прослеживаемые кольцевые подписи сублинейного размера без случайных оракулов». IEICE Transactions по основам электроники, связи и информатики . 95 (1): 393–415. Бибкод : 2012IEITF..95..151F . doi : 10.1587/transfun.E95.A.151 .

[7] Ау, Ман Хо; Лю, Джозеф К.; Сусило, Вилли; Юэнь, Цз Хон (2006). «Кольцевая подпись постоянного размера на основе идентификатора и отзывная кольцевая подпись, связанная с iff-связкой». Прогресс в криптологии - INDOCRYPT 2006 . Конспекты лекций по информатике. Том. 4329. стр. 364–378. дои : 10.1007/11941378_26 . ISBN 978-3-540-49767-7 .

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]

[ 6 ]

[ 7 ]