Вероятностная схема подписи Рабина

17-10-2021, 19:00

Вероятностная схема подписи Рабина — метод цифровой подписи, первоначально предложенный Михаэлем О. Рабином в 1979 году. Схема подписи Рабина была одной из первых предложенных схем цифровой подписи и является единственной, которая напрямую связывает сложность подделки подписи с проблемой целочисленной факторизации. Алгоритм подписи Рабина непригоден в случайной модели вычислений с оракулом, предполагающей, что проблема целочисленной факторизации неразрешима. Схема подписи Рабина также тесно связана с криптосистемой Рабина.

Оригинальный алгоритм

  • Генерация ключа
    • Выбираются простые числа p {displaystyle p} , q {displaystyle q} каждое приблизительно размера k / 2 {displaystyle k/2} бит и считается произведение n = p ⋅ q {displaystyle n=pcdot q} .
    • Далее выбирается случайное b {displaystyle b} из { 1 , … , n } {displaystyle {1,ldots ,n}} .
    • Открытым ключом является пара ( n , b ) {displaystyle (n,b)} .
    • Закрытым ключом соответственно ( p , q ) {displaystyle (p,q)} .
  • Подпись
    • Чтобы подписать сообщение m {displaystyle m} , подбирается случайное число U {displaystyle U} и вычисляется m ⋅ U mod n {displaystyle mcdot Umod n} .
    • Затем решается уравнение x ( x + b ) mod n = m ⋅ U mod n {displaystyle x(x+b)mod n=mcdot Umod n} .
    • Если решения уравнения не существует, выбирается новое значение U {displaystyle U} и заново решаем уравнение.
    • Подписью сообщения m {displaystyle m} будет пара ( U , x ) {displaystyle (U,x)}
  • Проверка
    • По данным сообщению m {displaystyle m} и подписи ( U , x ) {displaystyle (U,x)} верификатор V {displaystyle V} производит вычисления x ( x + b ) m o d n {displaystyle x(x+b)modn} и m ⋅ U mod n {displaystyle mcdot Umod n} и затем проверяет, что они равны.

Оригинальный алгоритм не использует хеш-функции и считается ненадежным.

Безопасный и упрощенный алгоритм

Безопасный и надежный алгоритм основан на хеш-функции, устойчивой к коллизиям H : { 0 , 1 } ∗ → { 0 , 1 } k {displaystyle H:{0,1}^{*} ightarrow {0,1}^{k}} .

В большинстве представлений алгоритм упрощается путем выбора b = 0 {displaystyle b=0} . Предполагается, что хеш-функция H {displaystyle H} с количеством выходных битов k {displaystyle k} является случайным оракулом и алгоритм работает следующим образом:

Генерация ключа
  • Выбираются простые числа p {displaystyle p} , q {displaystyle q} каждое приблизительно размером k / 2 {displaystyle k/2} бит, и p {displaystyle p} , q {displaystyle q} mod 4 равно 3. Далее вычисляется произведение n = p ⋅ q {displaystyle n=pcdot q} .
  • Открытым ключом в этом случае является n {displaystyle n} .
  • Закрытым ключом будет пара ( p , q ) {displaystyle (p,q)} .
  • Подпись
  • Чтобы подписать сообщение m {displaystyle m} , подбирается случайное число U {displaystyle U} и вычисляется H ( m , U ) {displaystyle H(m,U)} .
  • Если H ( m , U ) {displaystyle H(m,U)} не является квадратом по модулю n {displaystyle n} , выбирается новое значение U {displaystyle U} .
  • После находится одно значение x, которое является решением уравнения x 2 = H ( m , U ) mod n {displaystyle x^{2}=H(m,U)mod n} .
  • Подписью сообщения m {displaystyle m} будет пара ( U , x ) {displaystyle (U,x)} .
  • Проверка
  • По данным сообщению m {displaystyle m} и подписи ( U , x ) {displaystyle (U,x)} верификатор V {displaystyle V} производит вычисления x 2 m o d n {displaystyle x^{2}modn} и H ( m , U ) {displaystyle H(m,U)} и затем проверяет, что они равны.
  • Замечания

    В некоторых реализациях алгоритма величина U {displaystyle U} не используется. Вместо этого возможно ,в конечном итоге, умножить значение хеша на два числа a или b со свойствами ( a p ) = − ( a q ) = − 1 {displaystyle left({ frac {a}{p}} ight)=-left({ frac {a}{q}} ight)=-1} и ( b q ) = − ( b p ) = − 1 {displaystyle left({ frac {b}{q}} ight)=-left({ frac {b}{p}} ight)=-1} , где ( ⋅ ) {displaystyle (cdot )} обозначает символ Лежандра. Тогда для любого H {displaystyle H} по модулю n {displaystyle n} только одно из четырех чисел H , a H , b H , a b H {displaystyle H,aH,bH,abH} будет квадратом по модулю n {displaystyle n} , и именно оно выбирается для цифровой подписи сообщения.

    Чтобы еще больше упростить алгоритм, необходимо менять сообщение m {displaystyle m} до тех пор, пока подпись не пройдет проверку.

    Функция смены сообщения для верификации подписи def root(m: str, p, q): while True: x = h(m) sig = pow(p, q-2, q) * p * pow(x, (q+1)/4, q) sig = (pow(q, p-2, p) * q * pow(x, (p+1)/4, p) + sig) % (nrabin) if (sig * sig) % nrabin == x: print("Write extended message to file m.txt") f = open('m.txt', 'w') f.write(m) f.close() break m = m + ' ' return sig

    Безопасность

    Если хеш-функция H {displaystyle H} является случайным оракулом, то есть его выходные данные действительно случайны в Z / n Z {displaystyle mathbb {Z} /nmathbb {Z} } , то подделка подписи для любого сообщения m {displaystyle m} так же сложна, как вычисление квадратного корня случайного элемента из Z / n Z {displaystyle mathbb {Z} /nmathbb {Z} } .

    Чтобы доказать, что получение случайного квадратного корня так же сложно, как факторизация, необходимо отметить, что в большинстве случаев существует четыре различных квадратных корня, поскольку n {displaystyle n} имеет два квадратных корня по модулю p {displaystyle p} и два квадратных корня по модулю q {displaystyle q} , и каждая пара дает квадратный корень по модулю n {displaystyle n} по Китайской теореме об остатках. Некоторые из корней могут иметь одинаковое значение, но вероятность этого крайне мала.

    Если возможно найти два разных квадратных корня x {displaystyle x} , y {displaystyle y} таких, что x 2 = y 2 mod n {displaystyle x^{2}=y^{2}mod n} но x ≠ ± y mod n {displaystyle x eq pm ymod n} , то это немедленно приводит к факторизации n {displaystyle n} , так как на n {displaystyle n} делится x 2 − y 2 = ( x − y ) ( x + y ) {displaystyle x^{2}-y^{2}=(x-y)(x+y)} , но не делятся простые множители. Таким образом, вычисление gcd ⁡ ( x ± y , n ) {displaystyle operatorname {gcd} (xpm y,n)} приведет к нетривиальной факторизации n {displaystyle n} .

    Теперь предполагается, что существует эффективный алгоритм для нахождения хотя бы одного квадратного корня. Затем выбирается случайное r {displaystyle r} по модулю n {displaystyle n} и возводится в квадрат r 2 = R mod n {displaystyle r^{2}=Rmod n} ,после, используя алгоритм, берется квадратный корень от R {displaystyle R} по модулю n {displaystyle n} , и получается новый корень r ′ {displaystyle r^{prime }} , который с вероятностью 50% r ≠ ± r ′ mod n {displaystyle r eq pm r^{prime }mod n} .


  • Преобразование Хаусхолдера
  • Антикоммутативность
  • Класс BPP
  • Схема Шнорра
  • Матрица Адамара

  •  

    • Яндекс.Метрика
    • Индекс цитирования