Аналіз ефективності методу факторизації на еліптичних кривих. Практика

Проблема факторизації безпосередньо пов'язана з визначенням криптостійкості RSA, яке базується на припущенні, що не існує швидких алгоритмів факторизації, які за короткий час дали б зламати код, а якщо через деякий час і вийде це зробити, то дані втратять свою актуальність. У цій статті ми протестуємо і зробимо висновки по одному з методів факторизації.

Читати далі →

ЕЦП країн СНД на Python

image
Привіт!
Я вже писав на Хабре про своєї реалізації блокових шифрів країн СНД. Видалася ще одна вільна тиждень в результаті чого до симетричним стандартам додалися алгоритми електронного цифрового підпису: російський ГОСТ 34.10-2012, український ДСТУ 4145-2002 і білоруський СТБ 34.101.45-2013.
Всі три алгоритми засновані на еліптичних кривих. Але реалізація кожного із стандартів має свої тонкощі, про яких я хочу коротко розповісти в цій статті.

Читати далі →

Гіпотеза Берча - Свиннертон-Дайєра

Ця примітна гіпотеза пов'язує поведінку функції L там, де в даний час невідомо, визначено і порядок групи Ш, про яку невідомо, скінченна вона!
J. T. Tate, The arithmetic of еліптичні криві, Inventiones mathematicae 23 (1974)
ОригіналThis remarkable гіпотезу relates the behaviour of a function L at a point where it is not at present known to be defined to the order of a group Ш which is not known to be finite!(Коротка довідка щодо актуальності цитати 40-річної давності: після Уайлса і Ко таки стало відомо, що функцію L можна визначити на всій комплексній площині. Кінцівку групи Ш в загальному випадку залишається невідомою.)
Залишається обговорити можливість помилки. В якості заходів проти внутрішніх помилок комп'ютера можна прогнати всі обчислення двічі або робити перевірки всередині програми. Більше того, комп'ютери — на відміну від людей — влаштовані так, що їх помилки зазвичай надто великі, щоб їх не помітити. Ми впевнені, що в наших результатах немає подібних помилок. З іншого боку, при кодуванні хитромудрої схеми обчислень в комп'ютерну програму неминучі программистские помилки. Більшість з них виявляються ще до основних запусків, з-за того, що програма висне або видає безглузді результати. Але програма, яку вважається працює, все ще може містити логічні помилки, що виявляються при збігу рідкісних обставин: і дійсно, більшість комп'ютерів схильне аномалій, з-за яких ті іноді ведуть себе не так, як повинні по специфікаціям. По суті, наша програма для етапу (ii) виявилася неточною і пропустила дуже невелика кількість эквивалентностей, які повинна була знайти.

З цих причин ми вважаємо, що не варто автоматично довіряти результатам, отриманим на комп'ютері. У деяких випадках їх можна перевірити за рахунок властивостей, які по суті не були задіяні в обчисленнях і які навряд чи пережили б можливу помилку. (Наприклад, таблицю значень гладкої функції, отриману без використання інтерполяції, можна перевірити обчисленням різниць сусідніх значень. Але якщо подібні перевірки недоступні, не варто повністю довіряти результатам, поки вони не були незалежно підтверджені іншим програмістом на іншому комп'ютері. Ми не думаємо, що це задає надмірний стандарт у час, коли комп'ютери стають настільки широко доступні; і ми впевнені, що низькі стандарти вже призвели до публікації і вірі в невірні результати.

B. J. Birch and H. P. F. Swinnerton-Dyer, Notes on еліптичних кривих. I, Journal für die reine und angewandte Mathematik 212 (1963)
ОригіналIt remains to discuss the question of error. One can take precautions against machine errors either by running all the calculations twice checks or by included in the program. Крім того, machines — unlike human beings — are so designed that the errors they make are usually too gross to be overlooked. We are satisfied that there are in our no results undetected errors of this sort. On the other hand, in translating an розробити scheme of calculation into a machine program one is bound to make mistakes. Most of these are found before the program is used for production runs; they show up because the program grinds to a halt or produces ridiculous results. But a program which is believed to work may still contain logical errors which only have an effect in rare circumstances: and indeed most computers have anomalies which cause them occasionally not to behave in the way that their specifications suggest. In fact, our program for stage (ii) was imperfect in that a very few equivalences were missed by the machine.

For these reasons we believe that results obtained from a computer should not be automatically trusted. In some cases they can be checked because they have properties which were not essentially used in the course of the calculation and which would be unlikely to survive if an error had been made. (For example, if a table of a smooth function has been calculated without the use of interpolation, it can be checked by differencing.) But if checks sort of this are not available, results should not be fully trusted until they have been independently reproduced by a different programmer using a different machine. We do not think this sets an unreasonable standard, now that computers are becoming so widely available; and we are satisfied that lower standards have already led to a number of untrue results being and published believed.

Під катом не буде формулювання гіпотези; знаючі вислови на кшталт «Euler product» і «голоморфних continuation» (і в плані мови, і в плані конкретних понять) можуть прочитати п'ятисторінкову pdf з сайту інституту Клея. Під катом — деяка спроба пояснити, на якому напрямку розвитку математичної думки взагалі знаходиться гіпотеза Берча — Свиннертон-Дайєра. А також — як можна дорахувати до великих чисел, на зразок тих, що показані на КДПВ, менш ніж за секунду.

Читати далі →