Вероятностная схема подписи Рабина
Вероятностная схема подписи Рабина — метод цифровой подписи, первоначально предложенный Михаэлем О. Рабином в 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} является случайным оракулом и алгоритм работает следующим образом:
Генерация ключаЗамечания
В некоторых реализациях алгоритма величина 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} .