توصيفگر ها :
سيستم تبادل كليد , تبادل كليد ديفي-هلمن , آيزوجني , خم هاي بيضوي , گراف آيزوجني , خم هاي بيضوي ابرمنفرد
چكيده فارسي :
صداي پاي رايانه هاي كوانتوم به گوش مي رسد! چند دهه هست كه دانشمندان در جاي جاي جهان به دنبال ساخت رايانه هاي كوانتوم
هستند و دير يا زود اين اتفاق خواهد افتاد. با ورود رايانش كوانتوم، امكان پياده سازي الگوريتم هاي كوانتوم فراهم خواهد شد كه نتيجه
آن، شكستن سيستم هاي رمز نامتقارن معروف (و پراستفاده) و حل مسائل سخت مورد استفاده در رمزنگاري (مانند مسائل لگاريتم
گسسته روي Fp ،لگاريتم گسسته روي نقاط خم بيضوي و مسئله تجزيه) خواهد بود. حال با وجود قدرت بسيار زياد رايانه هاي
كوانتوم و فراگيرشدن زودهنگام آنها بايد زودتر از آن كه دير شود، به فكر جايگزين براي سيستم هاي رمز و به خصوص سيستم هاي
تبادل كليد موجود بود.
حداقل 5 گزينه شناخته شده براي جايگزيني به جاي پروتكل هاي مورد استفاده فعلي براي تبادل كليد در دوران پساكوانتوم وجود
دارد، تبادل كليد مبتني بر: مشبكه ها، كد، توابع درهم ساز، توابع چندمتغيره و آيزوجني ها. سيستم تبادل كليد ديفي-هلمن مبتني
بر آيزوجني روي خم هاي بيضوي ابرمنفرد كه مبتني بر آيزوجني هاست، يكي از بهترين مزايا را براي اين جايگزيني پيشنهاد
مي كند كه يك سيستم تبادل كليد پساكوانتوم هست كه حدود ده سال پيش (2011 (معرفي شده هست. منظور از پساكوانتوم بودن، اين
هست كه هنوز الگوريتم شناخته شده اي براي شكستن آن روي رايانه هاي كوانتوم - حتي با وجود قدرت بسيار زياد اين رايانه ها در
حل مسائل خاص- وجود ندارد.
سيستم تبادل كليد ديفي-هلمن مبتني بر آيزوجني ابرمنفرد، يك سيستم تبادل كليد براي ايجاد و توافق روي يك مقدار (كليد)
مشترك بين دو طرف هست؛ وجه تسميه اين سيستمِ تبادل كليد و اطلاق ديفي-هلمن به آن تشابه زياد آن به سيستم تبادل كليد معرفي
شده توسط ديفي و هلمن هست. در اين سيستم تبادل كليد، به صورت شهودي دو طرف از خم بيضوي ابرمنفرد از پيش مشخص شده
E) متناظر با عضو g (شروع مي كنند. دوطرف زيرگروه هاي مخفي A و B) متناظر با اعداد a و b (را انتخاب مي كنند و كليد عمومي
g (را محاسبه مي كنند. آنها پس از تبادل اطلاعات، خم A) /B/E ≃ (B) /A/E(
b
g و
a
خود يعني A/E و B/E) متناظر با
را محاسبه مي كنند و j-ثابت اين خم را به عنوان مقدار مشترك در نظر مي گيرند. مسائلي كه حل آنها منجر به شكستن امنيت اين
سيستم مي شود، مسئله آيزوجني ابرمنفرد يعني مسئله يافتن A با داشتن A/E) متناظر با مسئله لگاريتم گسسته) و مسئله ديفي هلمن
ابرمنفرد محاسباتي يعني يافتن B) /A/E (با داشتن A/E و B/E) متناظر با مسئله ديفي-هلمن محاسباتي ) هست.
در اين پايان نامه ابتدا به بيان مقدمات رياضي مورد نياز پرداخته و در ادامه به معرفي و بيان مراحل اين سيستم تبادل كليد، طريقه
ساخت پارامترهاي عمومي و نحوه انجام محاسبات خصوصي آن مي پردازيم. در ادامه به تشريح مجموعه اي از الگوريتم هاي سريع و
زمان ثابت براي آن خواهيم پرداخت.
چكيده انگليسي :
Abstract:
Quantum Computers are on the way! It’s several decades scientifics are trying to build quantum computers.
By the advent of quantum computing, it would be possible to implement quantum algorithms
that lead to the breakdown of well-known and widely-used asymmetric cryptosystems and to solve
hard problems that are used in cryptography (for example Discrete Logarithm Problem on the finite
fields and on the points of elliptic curve defined on finite fields and integers factoring). Now considering
this huge power of quantum computers, one should focus on post-quantum alternatives of
classic cryptosystems.
There are at least five well-known and commonly cited classes of cryptographic primitives that are
believed to remain secure in the presence of a quantum computer: code-based , lattice-based , hashbased
, multivariate and isogeny-based cryptography. Supersingular Isogeny Diffie-Hellman Key
Exchange(SIDH), that is based on isogenies and introduced about 10 years ago, is one of the best
candidates for this Replacement. SIDH is a post-quantum key exchange cryptosystem i.e. there is
no known algorithm either on quantum or classic computers that can break it. It is a key exchange
scheme for two parties to share a key and it called Diffie-Hellman. Because of the analogue between
SIDH and the traditional Diffie-Hellman protocol. To be more precise it’s a high level analogue between
them: In SIDH, Alice and Bob both start with Curve E (analogue to g); then they choose
subgroups A and B (analogue to integers a and b) and compute curves E/A and E/B (analogue
to g
a
and g
b
). After the public key exchange, they compute curve (E/A) /B ≃ (E/B) /A (analogue
to g
ab ) and use its j-invariant as the shared secret key. The problems that if they solve, SIDH
would break is CSSI problem (to find A from the known value E/A) and SSCDH problem(to find
(E/A) /B from the known values E/A and E/B).
In this thesis, we study SIDH. First we start with mathematical background about elliptic curve,
isogenies and isogeny graph. Then we discuss about its public parameters, secret computations and
security aspects . Finally we state a set of fast algorithms for SIDH from Costello and others.
In chapter 1 we focus on related basic mathematical subjects. Frist we state an introduction of
algebraic geometry and affine and projective space. Then we recall the definitions of elliptic curve,
isomorphism between them and j-invariant and the connection between them. Next, we express related
subjects to elliptic curves that are needed in the rest of the thesis such as torsion points, division
polynomials, Wail pairing, endomorphism and elliptic curves on finite fields.
In chapter 2 we focus on the most important maps between elliptic curves, isogenies. We state
the isogeny definition and its properties, the Velu’s formula (for computing isogenies) and finally, we
describe the isogeny graph and express some examples.
In chapter 3 we study SIDH. First , we describe traditional and elliptic curve forms of Diffie-Hellman
key-exchange and their underlying problems. Then we start discussion about SIDH that is introduced
by De Feo and Jao and express the techniques that they use for efficient computation. Then present
some known attacks to SIDH and its underlying problems.
Eventually, in chapter 4 we present Costello and other’s fast and constant-time algorithms for SIDH.
We express the techniques they use in their full-fledged implementation and show how they performed
point and isogeny computations in P
