1999 жылғы ашық кілттік криптография алгоритмі: Кэйли-Пурсер алгоритмі

Кіріспе

1999 жылғы ашық кілт криптографиялық алгоритмі

Кейли-Пурсер алгоритмі – 1999 жылдың басында 16 жасар ирланд қызы Сара Фланнери жариялаған, Дублиндегі деректерді қорғау компаниясы «Балтимор Технологиясы»-ның негізін қалаушы Майкл Пурсердің жарияланбаған жұмысына негізделген ашық кілт криптографиялық алгоритмі. Фланнери оны математик Артур Кейлидің есімімен атады. Кейіннен бұл алгоритмнің ашық кілт ретінде кемшіліктері бар екені анықталды, бірақ ол көптеп таралған бұқаралық ақпарат құралдарының назарына іліккен.

Тарих

Балтимор Технологиясымен жұмыс тәжірибесі кезінде Фланнериге Майкл Пурсердің жарияланбаған мақаласы көрсетілді, онда коммутативті емес көбейтуді пайдаланатын жаңа ашық кілттің криптографиялық схемасы сипатталған. Оған осы схеманы Mathematica тілінде іске асыруды жазу тапсырылды. Бұл тәжірибеден бұрын Фланнери 1998 жылғы ESAT жас ғалымдар мен технологиялар көрмесіне Цезарь шифрынан RSA-ға дейінгі, қазіргі кезде қолданылып жүрген криптографиялық әдістерді сипаттайтын жобасымен қатысқан. Бұл оған Intel студенттік сыйлығын жеңіп алды, соның арқасында 1998 жылы АҚШ-та өткен Intel International Science and Engineering Fair байқауына қатысуға мүмкіндік алды. Көрме жобасына өзіндік еңбегін қосу қажеттігін сезінген Фланнери Майкл Пурсерден оның криптографиялық схемасына негізделген жұмысты қосуға рұқсат сұрады. Математик әкесінің кеңесімен Фланнери Пурсердің схемасын іске асыру үшін матрицаларды пайдалануға шешім қабылдады, себебі матрица көбейтуінің қажетті коммутативті емес қасиеті бар. Нәтижедегі алгоритм көбейтуге байланысты болғандықтан, ол экспоненциалдық қадамды қолданатын RSA алгоритмінен әлдеқайда жылдам болар еді. Intel Science Fair жобасы үшін Фланнери RSA және оның жаңа Cayley–Purser алгоритмін қолданып, бірдей ашық мәтінді шифрлейтін демонстрациялық нұсқаны дайындады, және ол шынымен де уақытты айтарлықтай үнемдеді. 1999 жылы ESAT жас ғалымдар мен технологиялар көрмесіне оралған Фланнери Cayley–Purser алгоритмінің жұмыс уақытын формалдап, белгілі шабуылдардың әртүрлі түрлерін талдады, олардың ешқайсысы тиімді емес екені анықталды. Фланнери Cayley–Purser алгоритмінің RSA-ны алмастыратыны туралы ешқандай мәлімдеме жасамады, өйткені кез келген жаңа криптографиялық жүйе қауіпсіз жүйе ретінде мойындалу үшін уақыт сынағынан өтуі керек екенін білді. Бірақ бұқаралық ақпарат құралдары мұндай сақтық танытпады, және ол ESAT көрмесінде бірінші орын алғанда, әлемдегі газеттер жас гений қыз криптографияда революция жасады деп хабарлады. Шындығында, алгоритмге шабуыл жақын арада табылды, бірақ ол оны талдап, кейінірек оны қосымша ретінде қосты, соның ішінде Еуропа бойынша өткен байқауға да қосты, онда ол маңызды сыйлыққа ие болды.

During a work experience placement with Baltimore Technologies, Flannery was shown an unpublished paper by Michael Purser which outlined a new public key cryptographic scheme using non commutative multiplication. She was asked to write an implementation of this scheme in Mathematica. Before this placement, Flannery had attended the 1998 ESAT Young Scientist and Technology Exhibition with a project describing already existing cryptographic techniques from the Caesar cipher to RSA. This had won her the Intel Student Award which included the opportunity to compete in the 1998 Intel International Science and Engineering Fair in the United States. Feeling that she needed some original work to add to her exhibition project, Flannery asked Michael Purser for permission to include work based on his cryptographic scheme. On advice from her mathematician father, Flannery decided to use matrices to implement Purser's scheme as matrix multiplication has the necessary property of being non commutative. As the resulting algorithm would depend on multiplication it would be a great deal faster than the RSA algorithm which uses an exponential step. For her Intel Science Fair project Flannery prepared a demonstration where the same plaintext was enciphered using both RSA and her new Cayley–Purser algorithm and it did indeed show a significant time improvement. Returning to the ESAT Young Scientist and Technology Exhibition in 1999, Flannery formalised Cayley Purser's runtime and analyzed a variety of known attacks, none of which were determined to be effective. Flannery did not make any claims that the Cayley–Purser algorithm would replace RSA, knowing that any new cryptographic system would need to stand the test of time before it could be acknowledged as a secure system. The media were not so circumspect however and when she received first prize at the ESAT exhibition, newspapers around the world reported the story that a young girl genius had revolutionised cryptography. In fact an attack on the algorithm was discovered shortly afterwards but she analyzed it and included it as an appendix in later competitions, including a Europe wide competition in which she won a major award.

Шолу

Бұл талқылауда қолданылған белгілер Фланнеридің түпнұсқа мақаласындағы белгілермен сәйкес келеді.

Кілтті жасау

RSA сияқты, Кейли Пурсер екі үлкен жай санды p және q және олардың көбейтіндісі n-ді, яғни жартылай жай санды шығарудан бастайды. Содан кейін, GL(2,n) қарастырылады, ол бүтін элементтері бар 2×2 матрицалардың жалпы сызықтық тобы және n-ге модульдік арифметика. Мысалы, егер n=5 болса, мынаны жазуға болады: Бұл топ үлкен реті болғандықтан таңдалды (үлкен жартылай жай сан n үшін), ол (p²−1)(p²−p)(q²−1)(q²−q) тең. GL(2,n) тобынан екі осындай матрицаны таңдап, r деген табиғи санды таңдап, мыналарды есептейміз: Ашық кілт - , , және . Жасырын кілт - .