Суп, анон. Вот читал статью про Bitcoin и криптографию и не смог понять. Сама статья вот: https://self-evident.org/?p=976
В ней криптография объясняется на примере криптофункции Рабина. Если я правильно понял, то она работает так:
Предположим, я создал сообщение X и закодировал его большой цифрой Y. Правила кодирования всем известны и раскодировать Y может любой желающий. Но чтобы подтвердить, что Y - действительно создан мной - я применяю криптофункцию Рабина.
Выглядит она так: f(x) = square(x) | mod n
Где n = p*q, p и q = это простые числа (prime numbers).
n - мой публичный ключ, p и q - приватный ключ.
То есть, допустим, если p и q = 3 и 7 соответственно, а x, предположим, равен 12, то ф-ия будет выглядеть так:
f(12) = (12*12) / (3*7) = 144/21 = 6,857142857
Берем остаток 857142857 - это и есть результат работы этой функции.
Так вот, предположим, что мой y = 18. Тогда, чтобы подтвердить, что y создан мной, я беру и подбираю такой x для своей криптофункции, который после возведения в квадрат и деления на n оставит остаток, который и будет равняться моему сообщению y, то есть 18. Однако математики говорят, что, мол, если n - это произведение двух простых чисел, то быстро подобрать такой x можно, только зная p и q, то есть мой приватный ключ. Это доказано в т.н. Chinese Remainder Theorem. То есть другой человек не сможет найти число, квадрат которого после деления на мой публичный ключ n оставляет заранее заданный остаток, поэтому, даже если он знает, что f(x) = square(x) | mod n, знает y и знает n, то он не сможет подобрать x и не сможет подтвердить, что он создал Y.
Но вот чего я не могу понять:
Если мой n - 21, а y = 18, то чтобы найти x, я ведь могу просто умножить n, скажем, на 4, прибавить к нему остаток 18 и из полученного извлечь корень:
x = (4*21)+18 = 102
102/21 = 4 + 18 в остатке
Корень из 102 - и есть искомый x. Итак, ЧЯДН?