[Uneex] Задача по изобретению велосипеда на гусеничном ходу

[Fr. Br. George]

Всем привет.

Задача на реализацию части функциональностей электронной подписи в
жёстких условиях.

Условие. Есть некотрое число, достаточно большое для приличной схемы
шифрования с симметричным ключом и недостаточно -- для схемы с
ассиметричным ключом. Скажем, пятидесятизначное шестнадцатеричное. Из
всего диапазона таких чисел нужно очень мало, скажем, миллион. Это число
получено товарищем от нас в качестве пароля в записанном на бумажке
виде. Процедуры пророждения такого числа и проверки того, что число
порождено именно нами -- раздельные.

Задача: изобрести такие процедуры проверки и порождения, чтобы наши
товарищи могли беспрепятственно проверять правильность числа, но не
могли сами порождать эти числа.

Замечание: пользоваться можно чем угодно, нопример нашими открытыми
gpg-ключами и т. п., надо только иметь в виду, что информация, доступная
нашим товарищам отличается _только_ этим числом-паролем.

Соображение: подобная (?) ситуация возникает во всяких проприетарных
программах, трубующих код активации. И процентное соотношение общего
числа таких программ к числу программ, имеющих keygen, наводит на
мысль, что задача неразрешима. Доказательство неразрешимости также
является ответом. Но лучше бы она решалась :).

[2ivlad] Может, ты уже что-то знаешь?

-- 
			George V Kouryachy (aka Fr. Br. George)
			mailto:george at po_cs_msu_su