الگوريتم شور به زبان ساده؛ رمزگشايي داده در كامپيوتر كوانتومي
اگر جزو آن دسته از افرادي باشيد كه براي هر نوعي از تكنولوژي، جنبهي تاريك و خطرناكي ميبينند و معتقد هستند توسعهي هوش مصنوعي سرانجام به آخرالزمان رباتي، پايان برتري انسان و شروع حكمروايي رباتها ميانجامد، احتمالا با شنيدن رايانش كوانتومي نيز به جنبهي تاريك و ترسناك اين تكنولوژي نوظهور فكر كردهايد.
اين جنبهي تاريك كه گويا امنيت دادههاي رمزنگاريشده و رمزارزهايي مانند بيتكوين را به خطر مياندازد، دغدغهي بسياري از متخصصان اينترنتي است. از انديشه متخصصين آنها، پيشرفت بشر در توسعهي كامپيوترهاي كوانتومي ديگر اثري از امنيت و حريم شخصي در اينترنت بر جا نخواهد گذاشت.
اما اين ادعا چقدر به واقعيت نزديك است؟ يا چند سال با تبديل شدن به واقعيت فاصله دارد؟ اصلا كامپيوتر كوانتومي چگونه قفل دادههاي رمزنگاريشده را ميشكند؟ جواب «الگوريتم شور» (Shor's algorithm) است. اگر كنجكاويد بدانيد اين الگوريتم چطور كار ميكند و چگونه ميتواند در عرض چند دقيقه از دادهاي رمزگشايي كند كه در كامپيوتر معمولي ميليونها سال زمان ميبرد، با اين مقاله همراه باشيد.
كامپيوتر كوانتومي
بسياري از فناوريهايي كه امروزه به واسطهي عادت به حضورشان بهراحتي آنها را ناديده ميگيريم، مانند ترانزيستورهاي تلفنهاي همراه، LED چراغ قوه و دستگاههاي MRI، همه مديون مكانيك كوانتوم هستند. اما متخصصد ديگر مكانيك كوانتوم كه ساير فناوريهاي كنوني بهخوبي قادر به عملياتي كردن آن نيستند، محاسبات كوانتومي است كه روشي كاملا متفاوت براي ذخيرهسازي و پردازش داده ارائه ميدهد.
كامپيوترهاي كنوني اطلاعات را بهصورت بيتِ يك يا صفر (روشن/خاموش) ذخيره ميكنند و محاسبات را با استفاده از اجزاي كوچك پردازش الكترونيكي داده موسوم به «ترانزيستور» انجام ميدهند. در مقابل، كامپيوترهاي كوانتومي با تكيه بر كيوبيتها (بيت كوانتومي) ميتوانند تركيبي از يك و صفر را به لطف پديدهي برهمنهي كوانتومي (superposition)، بهصورت همزمان ذخيره كنند و اين تركيب تا زماني كه كيوبيت محاسبه نشده است، نامعلوم باقي خواهد ماند.
رايانش كوانتومي: برهمنهي و درهمتنيدگي
پديدهي برهمنهي كوانتومي كه در آن سيستم كوانتومي ميتواند در آن واحد در چندين حالت يا مكان ممكن حضور داشته باشد، شبيه پرتاب سكه است. تا زماني كه سكه در هوا در حال چرخش است، تنها چيزي كه مسلم است اين است كه احتمال شير يا خط آمدن نصفنصف است؛ اما به محض فرود سكه و نگاه كردن به آن ميتوان با قطعيت گفت كدام روي سكه قابل مشاهده است. به عبارت ديگر ميتوان گفت مادامي كه سكه در حال چرخش است، در آن واحد هم شير است و هم خط.
در مورد محاسبات رياضي به كمك رايانش كوانتومي هم اين حالت وجود دارد. در كامپيوتر كوانتومي، ذرات (الكترون يا فوتون)، به كمك ليزرهايي با دقت بسيار بالا يا پرتوهاي مايكروويو در حالت برهمنهي قرار گرفته و هميشه در حال نوسان هستند. حالت اين ذرات تا زماني كه مقاديرشان اندازهگيري نشده است، معلوم نيست. اما اگر تمام حالتهايي كه اين ذرات ممكن است به خود بگيرد شناخته شده باشد، آن وقت ميتوان گفت آنها همزمان در تمام آن حالتهاي ممكن وجود دارند.
ازآنجاكه هر كيوبيت هر دو حالت صفر و يك بيت را در خود ذخيره ميكند، به تعداد N كيوبيت ميتوان همزمان دو برابر حالتهاي ممكن دادهي ذخيرهشده در بيت را ذخيره كرد. اين مقدار بسيار قابل توجهي است؛ در جهان ۱۰ به توان ۷۸ تا ۱۰ به توان ۸۲ اتم قابل مشاهده وجود دارد و ۲۶۵ كيوبيت ميتواند همزمان به اندازهي تمام اتمهاي جهان در خود داده ذخيره كند.
علاوه بر پديدهي برهمنهي، كيوبيتها ويژگي مهم ديگري نيز دارند كه به آن درهمتنيدگي (entanglement) ميگويند. در اين حالت، تغيير رفتار يكي از دو كيوبيت درهمتنيده شده بلافاصله در رفتار كيوبيت دوم بهصورت كاملا پيشبينيشدهاي تغيير ايجاد ميكند. در پديدهي درهمتنيدگي اتفاق بسيار شگفتانگيزي رخ ميدهد و آن تأثير دو كيوبيت درهمتنيده بر يكديگر در فواصل بسيار طولاني است.
به عبارتي، ذرات درهمتنيده حتي اگر كيلومترها با هم فاصله داشته باشند، همچنان تغيير حالت يكي بر ديگري تأثير ميگذارد. در كامپيوتر معمولي دو برابر كردن تعداد بيتها قدرت پردازش آن را دوبرابر ميكند؛ اما به لطف پديدهي درهمتنيدگي، افزايش تعداد كيوبيتها در دستگاه كوانتومي منجر به افزايش تصاعدي در سرعت پردازش اطلاعات ميشود.
پديدهي درهمتنيدگي بسيار شبيه جادوگري به انديشه متخصصين ميرسد و فيزيكدانان هم بهطور كامل از سازوكار آن سر در نميآورند (حتي اينشتين هم آن را «رفتار عجيب و اسرارآميز در فاصلهي دور» ناميد!)؛ اما در حوزهي رايانش كوانتومي، اين پديده كمك ميكند حتي در صورت عدم قطعيت، اطلاعات از جايي بهجاي ديگر منتقل شود. مثل اين ميماند از سكهي كه هنوز در حال چرخش است، براي حل محاسبات پيچيده استفاده كرد. با اتصال چندين كيوبيت به يكديگر ميتوان مسائلي را حل كرد كه حتي سريعترين كامپيوترهاي غير كوانتومي براي حل آنها به ميليونها سال زمان نياز دارند.
تصور غلط در مورد كامپيوتر كوانتومي
در مورد طرز كار كامپيوتر كوانتومي اين تصور رايج وجود دارد كه چندين كامپيوتر معمولي در كنار هم و همزمان با هم روي مسئلهاي واحد كار ميكنند؛ اين تصور تا حدودي هم درست و هم نادرست است.
وقتي ميگوييم كامپيوتر كوانتومي تعدادي كامپيوتر معمولي است كه در موازات يكديگر مشغول حل مسئلهاي واحد هستند، در واقع منظور اين است كه كامپيوتر كوانتومي در حالت برهمنهي تمام حالتهايي است كه كامپيوتر معمولي ميتواند به خود بگيرد. در واقع اگر N حالت پايه داشته باشيم، براي هر حالت، احتمال يك N-ام وجود دارد و كامپيوتر كوانتومي بهجاي قرار داشتن در تمام اين حالتها بهصورت يك حالت واحد، انگار خودش را به N حالت ممكن تجزيه كرده است.
كامپيوتر كوانتومي تمام پاسخهاي ممكن را نشان نميدهد
به عبارت ديگر، اگر مسئلهاي را در كامپيوتر كوانتومي وارد كنيد و از جواب آن خروجي بگيريد، كامپيوتر تمام حالتها و جوابهاي ممكن را به شما نشان نميدهد، بلكه تنها يكي از اين جوابهاي ممكن با احتمال يك N-ام را بهطور كاملا تصادفي انتخاب ميكند و به شما ميگويد چيست.
در نتيجه مشاهدهي تمام اين حالتها و جوابها ممكن نيست و رايانش كوانتومي در پايان تنها يك جواب را بهصورت رندوم نمايش ميدهد. به قول اسكات آرونسون، دانشمند علوم انديشه متخصصيني، اين طور نيست كامپيوترهاي كوانتوم براي حل مسائل بسيار دشوار و پيچيده تمام راهحلهاي ممكن را همزمان و در لحظه مطالعه كنند تا به جواب درست برسند. براي كامپيوتر كوانتوم در حالت كلي هيچ فرقي بين جواب درست و نادرست وجود ندارد و بعد از پايان محاسبات، تنها يك جواب را آن هم بهطور كاملا تصادفي نشان خواهد داد.
در ادامه و در بخش طرز كار الگوريتم شور خواهيم ديد محققان چگونه به كمك الگوريتمي براي اعمال «برهمنهي ويرانگر»، تمام حالتهاي نادرست را خنثي ميكنند و به كمك «برهمنهي سازنده»، پاسخ درست را تقويت ميكنند تا انتخاب رايانش كوانتومي باشد.
نگرانيهاي امنيتي رايانش كوانتومي
سالها پيش از اينكه سرگئي برين و لري پيج با توسعهي موتور جستجوي گوگل به شكلگيري اينترنت كنوني كمك كنند، پيتر شور، استاد آمريكايي رياضيات متخصصدي در دانشگاه MIT، مقالهاي الگوريتمي منتشر كرد كه ميتوانست در آينده قفل تمام رمزنگاريهاي ارتباطاتي را بشكند.
شور هكري با نيتي شرورانه نبود، بلكه رياضيداني بود كه در مركز آزمايشي بل لبز مانند رياضيدانهاي مثل خودش دنبال حل مسائل دشوار رياضي ميگشت. الگوريتم او كه به الگوريتم شور (Shor’s Algorithm) معروف است، به نوعي فناوري نياز داشت كه در زمان انتشار مقاله در سال ۱۹۹۴ به زحمت در سطح انديشه متخصصينيه مطرح شده بود و تا رسيدن به مرحلهي عملياتي به سالها زمان نياز داشت.
تا چند سال بعد از انتشار الگوريتم شور هنوز دليلي براي نگراني امنيت ارتباطات اينترنتي وجود نداشت، چرا كه كامپيوترهاي آن زمان به هيچوجه قادر به استفاده از اين الگوريتم براي شكستن رمزنگاري داده نبودند. اما با گذر زمان و پيشرفت تكنولوژي در حوزهي كامپيوتر كوانتومي (كه الهام گرفته از الگوريتم شور است)، كمكم اين نگراني ايجاد شد كه اين الگوريتم ميتواند بهراحتي امنيت بخش زيادي از اطلاعات رمزنگاريشده در بستر اينترنت را به خطر بيندازد.
امنيت رمزنگاري داده بر اساس «بيتهاي امنيت» سنجيده ميشود. براي مثال، مهاجم سايبري براي رمزگشايي از دادهاي كه با كليد ۱۲۸ بيتي AES (استاندارد رمزنگاري پيشرفته)، يا با كليد ۲۵۶ بيتي منحني بيضوي (Elliptic-curve cryptography) يا كليد ۳۰۷۲ بيتي RSA رمزنگاريشده است، به انجام ۲۱۲۸ مرحلهي محاسباتي نياز دارد. به عبارت ديگر، هر كدام از اين سه روش براي رمزنگاري داده، داراي ۱۲۸ بيت امنيت است.
اما تعداد مراحل محاسباتي براي رمزگشايي داده به نوع كامپيوتر بستگي دارد. ۱۲۸ بيت امنيت براي دادهاي كه با كليد ۳۰۷۲ بيتي RSA رمزنگاريشده است، تنها حملاتي صدق ميكند كه با كامپيوتر معمولي صورت گرفتهاند نه با كامپيوتر كوانتومي. ماهيت كامپيوترهاي كوانتومي اين امكان را ميدهد تا الگوريتمهايي مانند شور بهراحتي اجرا شوند و امنيت برخي الگوريتمهاي رمزنگاري را با تهديد جدي روبهرو كنند.
در عين حال بايد دانست رمزنگاري داده ضمانت صددرصدي براي حفظ امنيت اطلاعات نيست، بلكه تنها راهي است تا دسترسي هكرها را به داده آنقدر دشوار كند تا آنها از فكر هك كردن داده منصرف شوند. اما كامپيوترهاي كوانتومي اين پتانسيل را دارند تا دسترسي به دادهي رمزنگاريشده را بهشدت آسان كنند. در واقع الگوريتم شور مانند شمشير نوري در فيلم جنگ ستارگان عمل ميكند كه قادر است هر قفل و مانعي را بهراحتي از سر راه خود بردارد.
رمزنگاري دسترسي هكرها به داده را دشوار ميكند اما از بين نميبرد
اين الگوريتم امنيت كليد ۳۰۷۲ بيتي RSA را از ۱۲۸ بيت به تنها ۲۶ بيت كاهش ميدهد. براي درك بهتر از امنيت ۲۶ بيتي كافي است بدانيد قدرت محاسباتي موبايل همراه شما بهراحتي قادر است چنين دادهاي را در عرض چند دقيقه رمزگشايي كند. اين در حالي است كه براي رمزگشايي از برخي كليدهاي امنيتي با كامپيوترهاي معمولي به چند ميليون سال زمان نياز است.
براي تصور بهتر اين موضوع، خوب است بدانيد كليد رمزنگاري ۲۵۶ بيتي شامل دو به توان ۲۵۶ تركيب ممكن است. اين يعني:
۱۱۵,۷۹۲,۰۸۹,۲۳۷,۳۱۶,۱۹۵,۴۲۳,۵۷۰,۹۸۵,۰۰۸,۶۸۷,۹۰۷,۸۵۳,۲۶۹,۹۸۴,۶۶۵,۶۴۰,۵۶۴,۰۳۹,۴۵۷,۵۸۴,۰۰۷,۹۱۳,۱۲۹,۶۳۹,۹۳۶ تركيب ممكن (عدد ۷۸ رقمي). حتي سريعترين اَبَركامپيوتر دنيا، يعني Tianhe-2، براي رمزگشايي از اين كليد به ميليونها سال زمان نياز دارد.
اگر مهندسان موفق شوند كامپيوترهاي كوانتومي با تعداد بسيار زيادي كيوبيت (هزاران كيوبيت) توليد كنند و دست مهاجمان سايبري به اين كامپيوترها برسد، آن وقت امنيت الگوريتم RSA و روشهاي رمزنگاري مشابه بهطور كامل نابود ميشود.
رمزنگاري RSA
براي درك طرز كار الگوريتم شور لازم است ابتدا با طرز كار الگوريتم رمزنگاري RSA آشنا شويد. اين الگوريتم كه براي رمزنگاري هر چيزي، از فايلهاي روي هارد درايو گرفته تا ترافيك محرمانهي اينترنتي، به كار ميرود، از نوع نامتقارن يا به روش كليد عمومي است؛ به اين معني كه رمزنگاري با كليدي انجام ميشود كه در دسترس عموم است؛ اما رمزگشايي با كليد خصوصي كه در تنها در اختيار متخصص اصلي است، امكانپذير است. اين روش رمزنگاري براي مواقعي به كار ميرود كه متخصصي كه داده را رمزنگاري كرده است، روشي امن و مطمئن براي به اشتراك گذاشتن كليد با متخصص دوم در اختيار ندارد.
ويژگي ديگر رمزنگاري RSA استفاده از عمليات ضرب دو عدد اول است (N= a.b) كه حاصل آن (N) همان دادهي رمزنگاريشده است. انجام عمليات ضرب بسيار آسان است و هر كامپيوتري از پس محاسبهي آن بهراحتي برميآيد. اما سختي كار جايي است كه قرار است اين عمليات بهصورت معكوس انجام شود. يعني اگر از شما بپرسند عدد ۷۰۱۱۱۱ از ضرب كدام دو عدد اول به دست آمده است، آيا ميتوانيد جواب را پيدا كنيد؟
پيدا كردن جواب اين مسئله حتي با ماشينحساب يا كامپيوتر امكانپذير نيست. درحاليكه اگر سؤال اين بود كه حاصل ضرب ۹۰۷ در ۷۷۳ چقدر ميشود، با همان ماشينحساب بهراحتي ميتوانستيد به جواب ۷۰۱۱۱۱ برسيد. اين دو عدد درواقع همان اعداد اولي هستند كه در سؤال قبلي قرار بود آنها را پيدا كنيم؛ اما هيچ راهي براي رسيدن به آن نداشتيم.
رمزنگاري RSA از ضرب دو عدد اول بسيار بزرگ براي رسيدن به عددي بسيار بزرگتر استفاده ميكند
ويژگي جالب ديگر اين محاسبه اين است كه با داشتن يكي از اين دو عدد اول، رسيدن به عدد دوم بسيار آسان است. كافي است حاصل ضرب (N) را به اين عدد تقسيم كنيم تا عدد دوم به دست آيد.
ازآنجاكه محاسبهي رابطهي بين اين اعداد از يك سو آسان و از سوي مخالف بهشدت دشوار است، به آن تابع دريچه (trapdoor function) ميگويند. در رمزنگاري RSA براي هرچه دشوارتر كردن حدس اين دو مضرب، از اعداد بسيار بسيار بزرگ استفاده ميشود. براي مثال، كليد ۲۰۴۸ بيتي RSA براي رمزنگاري داده از كليدي استفاده ميكند كه از ۶۱۷ رقم تشكيل شده است.
ممكن است براي برخي اين سؤال پيش آمده باشد كه چطور الگوريتمي مانند RSA كه فقط با اعداد و ارقام سروكار دارد، ميتواند پيامي مثل «براي من ساندويچ بخر» را رمزنگاري كند. جواب اين است كه تمام اطلاعاتي كه در كامپيوتر پردازش ميشود بهصورت باينري (صفر و يك) ذخيره شدهاند و از استانداردهاي كُدبندي نويسه مانند يونيكد (Unicode) يا اسكي (ASCII) براي نمايش دادن آنها بهصورت حروفي كه براي انسان قابلفهم باشند، استفاده ميشود.
اين به اين معني است كه پيامي مانند «براي من ساندويچ بخر» در كامپيوتر بهصورت صفر و يك كدنويسي شده است و بهراحتي ميتواند به شكل زنجيرهاي از اعداد در الگوريتم RSA رمزنگاري شود.
با اين اوصاف ميتوان گفت دشواري شكستن رمزنگاري RSA در دو لايه مطرح ميشود: ۱- اعدادي كه در اين الگوريتم استفاده ميشوند به حدي بزرگ هستند كه دستيابي به كليد خصوصي با آزمون و خطا ممكن نيست. ۲- كامپيوترهاي كنوني براي پيدا كردن مضربهاي اول اين اعداد بسيار بزرگ به ميليونها يا شايد ميلياردها سال محاسبه نياز دارند.
طرز كار الگوريتم شور به زبان ساده
الگوريتم شور اگرچه در عمل، عمليات پيچيدهاي است اما ساختار اصلي آن به طرز شگفتانگيزي ساده است.
همانطور كه گفته شد در رمزنگاري RSA، از حاصل ضرب دو عدد اول، عدد بسيار بزرگ N حاصل ميشود. فردي كه بتواند اين دو عدد اول را پيدا كند، در واقع توانسته از داده رمزگشايي كند. اما پيدا كردن اين دو عدد اول تقريبا غير ممكن است، مگر اينكه از الگوريتم شور در كامپيوتر كوانتومي استفاده شود.
طبق اين الگوريتم، هر حدس رندوم و بياساس (g) از عددي كه ممكن است مضربي از N باشد، اگر به توان p/2 برسد و يك واحد به آن اضافه يا كم شود، به جواب درست بسيار نزديكتر است. به انديشه متخصصين ساده است، به شرطي كه بتوانيم مقدار p را پيدا كنيم. مقدار p را هم ميتوان تقريبا بلافاصله و با انجام تنها يك محاسبهي كوانتومي موسوم به تبديل فوريه (Fourier transform)، كه البته كمي پيچيده است، به دست آورد.
پس در الگوريتم شور كار را با حدس عددي رندوم شروع ميكنيم كه ممكن است مضربي از عدد N باشد (اما به احتمال زياد نيست) و بعد اين الگوريتم اين حدس رندوم را به حدس خيلي بهتري كه احتمالا مضربي از N باشد، تبديل ميكند.
در اين فرايند هيچ فيزيك كوانتومي دخيل نيست و ميتوان آن را روي كامپيوترهاي معمولي براي پيدا كردن مضربهاي عددي بزرگ اجرا كرد. اما چالش اصلي مدتزمان بسيار زيادي است كه لازم است كامپيوتر معمولي حدس رندوم و غير محتمل ما را به حدس بهتري كه احتمالا جواب درست باشد، تبديل كند. مثلا پيدا كردن دو مضرب عددي كه ۵۰ رقم دارد شايد روي كامپيوتر معمولي چند دقيقه طول بكشد؛ اما اگر اين عدد ۲۳۲ رقم داشته باشد، سالها زمان لازم است تا دو مضرب آن پيدا شود. در واقع در سال ۲۰۰۹، تيمي ۱۲ نفره از محققان براي پيدا كردن دو مضرب N با ۲۳۲ رقم، دو سال زمان صرف كردند.
نكتهاي كه دربارهي كامپيوتر كوانتومي بايد در انديشه متخصصين گرفت اين است كه قرار نيست مسائلي را حل كند كه براي آنها هيچ جواب محتملي پيشبيني نشده است، بلكه اين مدل كامپيوترها تنها سرعت رسيدن به جواب را افزايش ميدهند؛ البته افزايشي بسيار چشمگير، بهطوريكه حل مسئله را از ميليونها سال زمان به تنها چند دقيقه كاهش ميدهد.
اما الگوريتم شور چگونه حدس رندوم و غير محتمل ما را به حدس بهتري تبديل ميكند (فرايند كاملا رياضياتي) و چرا كامپيوتر كوانتوم اين فرايند را تسريع ميكند (عمليات فيزيكي)؟
همه چيز با عدد بزرگ N شروع ميشود كه قرار است مضربهاي آن را پيدا كرده تا به اين ترتيب قفل اطلاعات رمزنگاريشده را بشكنيم. اين دو مضرب براي ما نامعلوم است، براي همين عددي كوچكتر از N را بهعنوان حدس اوليه خود انتخاب ميكنيم. نكتهي قابلتوجه اين است كه نيازي نيست عددي كه حدس ميزنيم حتما مضرب اصلي N باشد. اين حدس ميتواند عددي باشد كه در مضربي با N مشترك است؛ مثلا ۴ مضربي از ۶ نيست؛ اما هر دو در مضرب ۲ با هم مشترك هستند.
الگوريتم شور حدس رندوم را به حدس بهتري تبديل ميكند
علت اينكه ميتوان اعدادي را كه با N مضرب مشترك دارند براي اين الگوريتم در انديشه متخصصين گرفت، اين است كه به كمك الگوريتم اقليدس ميتوان بهراحتي بزرگترين مقسوم عليه مشترك دو عدد (بزرگترين عددي كه هر دو به آن بخشپذيرند و باقيمانده صفر است) را پيدا كرد كه اين عدد همان مضربي از N است كه به دنبال آن هستيم.
درنتيجه براي حدس مضربي از N لازم نيست خود عدد را حدس بزنيم، بلكه حدس زدن اعدادي كه در مضربي از N مشترك هستند كفايت ميكند. در صورتي كه الگوريتم اقليدس بتواند مضربي مشترك با N پيدا كند، كار تمام است. كافي است N را بر آن مضرب تقسيم كنيم تا عدد دوم به دست آيد و به اين ترتيب با در اختيار داشتن هر دو مضرب N ميتوانيم داده را رمزگشايي كنيم.
اما داستان به اين سادگيها هم نيست. براي اعداد بسيار بزرگي كه در رمزنگاري به كار ميروند، اينكه هر حدس در مضربي از N مشترك باشد تا حد نجومي غير محتمل است. براي همين در اين الگوريتم از ترفندي استفاده ميشود تا حدس غير متحمل به حدسي تبديل شود كه احتمال داشتن مضرب مشتركي با N در آن زياد باشد.
اين ترفند بر اساس يك قاعدهي سادهي رياضي است: براي هر جفت عدد صحيحي كه با يكديگر مضرب مشتركي ندارند (مثلا N و g)، اگر يكي از آنها را (g) به اندازهي كافي در خودش ضرب كنيد (p)، سرانجام به عدد صحيحي خواهيد رسيد كه مضربي از عدد دوم (m.N) بهعلاوهي يك است.
براي مثال فرض كنيد N عدد ۱۵ و حدس اوليهي ما بهعنوان يكي از دو مضرب ۱۵، عدد ۷ است (چون ۱۵ عدد بسيار كوچكي است، واضح است ۷ مضربي از آن نيست؛ اما براي اعداد بزرگتر نميتوان در همان نگاه اول مشخص كرد حدس رندوم ما جواب درست است يا خير). درحاليكه عدد ۷ به توان ۲ مساوي مضربي از ۱۵ به اضافهي يك نيست و ۷ به توان ۳ هم اينطور نيست؛ اما ۷ به توان ۴ دقيقا مساوي مضربي از ۱۵ به اضافهي يك است؛ يعني مقدار p در اين معادله برابر ۴ است.
پس براي عدد بزرگ N و حدس غير محتمل g، ميتوان مطمئن بود تواني از g مساوي مضربي از N به اضافهي يك است. با جابجايي هوشمندانهي اين معادله، ميشود آن را به اين صورت بازنويسي كرد:
به اين ترتيب معادلهاي داريم كه شبيه اين است: (چيزي) ضرب (چيز ديگري) مساوي N است و اين دو دقيقا همان اعدادي است كه دنبال آن هستيم: دو مضرب N. به اين ترتيب الگوريتم شور حدس رندوم ما را به كمك اين فرمول به اعدادي تبديل ميكند كه مضربي از N است و به عبارت ديگر، خود اين دو عدد احتمالا مضاربي از دو مضرب اصلي N باشند. براي رسيدن به خود N كافي است از الگوريتم اقليدس كمك بگيريم.
مثلا:
اما ۵۰ و ۴۸ هيچكدام مضربي از ۱۵ نيست؛ اما به كمك ب.م.م ميتوان بين ۵۰ و ۱۵ عدد ۵ و بين ۴۸ و ۱۵ عدد ۳ را به دست آورد. ۵ و ۳ دو مضرب ۱۵ (N) هستند و به اين ترتيب داده رمزگشايي ميشود.
اما مكانيك كوانتوم كجاي اين داستان است؟ چرا همين حالا و با همين كامپيوترهاي معمولي نميتوان قفل اطلاعات رمزنگاريشده را شكست؟
مسئله اين است كه رسيدن به اين حدسهاي جديد و بهبوديافته ما را با سه اشكال روبهرو ميكند:
اولين اشكال اين است كه يكي از حدسها ممكن است خود مضربي از N باشد كه در اين شرايط حدس دوم مضربي از m خواهد بود و هيچ كدام به كار ما نميآيد، چون اين فرمول به عددي نياز دارد كه مضربي از N نباشد و تنها مضربي از آن با مضربي از N مشترك باشد تا بتوان به كمك الگوريتم اقليدس جواب اصلي را پيدا كرد.
اشكال دوم اين است كه p عدد فرد باشد كه در اين صورت حاصل تقسيم p بر ۲، عدد صحيح نخواهد بود كه اين هم به كار ما نميآيد.
اما براي هر حدس تصادفي، حداقل در سههشتم موارد اين احتمال وجود دارد كه هيچ يك از اين دو اشكال پيش نيايد و p حدسهايي ايجاد كند كه مضاربي از N باشند و رمز را بشكنند. اين احتمال ارزش تكرار دارد. براي هر حدس اوليه حداقل در ۳۷٫۵ درصد موارد اين احتمال وجود دارد كه g^p/2 ±1 به مضربي از N بيانجامد؛ اين يعني ۹۹ درصد اين احتمال وجود دارد تا تنها با ۱۰ حدس، به مضارب N برسيم و داده را رمزگشايي كنيم.
اما اشكال سوم به اين سادگي قابل حل نيست. براي تبديل حدس غير محتمل به حدس خوب لازم است آن را آنقدر در خودش ضرب كنيم تا به مضربي از N به اضافهي يك برسيم. براي كامپيوتر معمولي پيدا كردن اين توان (p) زمان و كار زيادي ميبرد. اينجا است كه پاي مكانيك كوانتوم به داستان باز ميشود و كل اين فرايند را به طرز جنونآميزي سرعت ميبخشد.
برخلاف محاسبات معمولي كه براي هر دادهي وارد شده تنها يك جواب ارائه ميدهد، محاسبات كوانتومي به كمك پديدهي برهمنهي قادر است بهطور همزمان چندين جواب ممكن را براي هر داده محاسبه كند؛ اما در آخر فقط يك جواب و آن هم بهصورت كاملا رندوم محاسبه ميشود.
كليد محاسبات سريع كوانتومي در رسيدن به نوعي برهمنهي كوانتوم است كه تمام جوابهاي ممكن را همزمان محاسبه كند و در عين حال بهطور كاملا هوشمندانهاي تمام جوابهاي نادرست را در حالت برهمنهي ويرانگر (destructive interference) قرار بدهد تا يكديگر را خنثي كنند. در اين حالت وقتي جواب مسئله محاسبه ميشود، خروجي ديگر رندوم نيست و به احتمال زياد جواب درست است.
ما در اين معادله دنبال عدد p هستيم. عدد p در واقع به period (دوره) اشاره ميكند و داراي خاصيت تناوبي است به اين معني كه اگر يك توان رندوم (x) را در انديشه متخصصين بگيريم و اندازهي p را به آن اضافه (يا از آن كم) كنيم، مقداري كه به اضافهي مضربي در N است (يعني r)، همواره يكسان باقي خواهد ماند.
مثلا اگر:
آنوقت
و
به اين ترتيب به هر تعداد مقادير p به توان رندوم g اضافه كنيم، جواب معادله هميشه به اندازهي يكسان (اينجا ۳) از مضربي از N بيشتر است. در اين حالتِ برهمنهي، اعدادي در اختيار داريم كه بهطور تناوبي به اندازهي دورهي p تكرار ميشوند يا به عبارت ديگر، به اندازهي فركانس يك بر p تكرار ميشوند. اگر بتوانيم اين فركانس را پيدا كنيم، ميتوانيم مقدار p را پيدا كنيم و با داشتن مقدار p و قرار دادن آن در فرمول ميتوانيم دو مضرب N را پيدا و داده را رمزگشايي كنيم.
بهترين ابزار براي پيدا كردن فركانس، تبديل فوريه (Fourier transform) است كه سيگنالهاي صوتي را به موج را تبديل ميكند و آن را بهصورت نموداري از توابع سينوس و كسينوس براي نمايش فركانسهاي مختلف تشكيلدهندهي موج نشان ميدهد.
نسخهي كوانتومي تبديل فوريه به محققان اين امكان را ميدهد تا با اعمال آن به برهمنهي كوانتومي كه با فركانس يك بر p تكرار ميشود، تمام فركانسهاي نادرست ممكن را در تداخل ويرانگر قرار داده تا همديگر را از بين ببرند (موجي با دامنهي صفر) و تنها يك حالت كوانتوم در آخر باقي بماند؛ يعني همان عدد يك بر p.
با معكوس كردن يك بر p، به p ميرسيم و مادامي كه p عدد زوج باشد (كه از تقسيم آن بر ۲، عدد صحيح حاصل شود) ميتوانيم حدس اوليهي خود را به توان اين عدد تقسيم بر دو برسانيم و به اندازهي يك واحد به آن اضافه و از آن كم كنيم. تا زماني كه به مضرب دقيقي از N نرسيم، ميتوانيم مطمئن باشيم حدس ما حالا در مضربي از N شريك است. با استفاده از الگوريتم اقليدس ميتوانيم اين دو مضرب را بهسرعت پيدا و به اين ترتيب داده را رمزگشايي كنيم.
كامپيوتر معمولي براي تست تمام مقادير ممكن براي p بايد اين مراحل را براي هر توان جداگانه انجام بدهد و بدين ترتيب سالها طول خواهد كشيد تا براي مقادير بسيار بزرگ N بتواند مقدار p را بهدرستي محاسبه و سرانجام مضربهاي N را پيدا كند. اما كامپيوتر كوانتوم تمام اين مقادير ممكن را در آن واحد محاسبه ميكند و تبديل فوريه تمام حالتهاي نادرست را در برهمنهي ويرانگر قرار داده تا جواب نهايي همان مقدار درست p باشد.
به اين ترتيب الگوريتم شور با حدس درست مضربهاي N، عملا رمزنگاريهاي كنوني را كه بر پايهي ضرب دو عدد اول هستند، بيفايده ميكند.
براي درك بهتر از طرز كار الگوريتم شور ميتوانيد ويدئوي زير را تماشا كنيد. در اين ويدئو به كمك اين الگوريتم دو مضرب عدد ۳۱۴۱۹۱ به دست ميآيد:
تماشا در يوتيوب
تهديد چقدر جدي است؟
زماني كه شور الگوريتم خود را مطرح كرد، خبري از رايانش كوانتومي در عمل نبود. ايدهي آن مدتي سر زبانها افتاده بود اما فقط در حد تئوري بود و هيچكس آن زمان فكر نميكرد ساخت كامپيوتر كوانتوم عملي باشد يا اصلا نيازي به ساخت آن باشد چون كامپيوترهاي معمولي ظاهرا از پس حل تمام محاسباتي كه لازم بود، برميآمدند.
اما پيتر شور نشان داد كامپيوتر كوانتومي فرضي ميتواند يك مسئلهي رياضي حلنشدني را بدون نياز به انجام محاسبات جداگانه براي مقادير مختلف، بهراحتي حل كند؛ و بدين ترتيب كنجكاوي و اشتياق محققان سراسر جهان را براي ساخت كامپيوترهاي كوانتومي برانگيخت.
اگرچه بسياري الگوريتم شور را پاياني براي امنيت رمزنگاري RSA و در نتيجه تهديدي جدي براي بيتكوين و ديگر رمزارزها در انديشه متخصصين ميگيرند، نگراني براي اين موضوع در حال حاضر بسيار زود است.
مسئله اين است كه تعامل كيوبيتها با محيط اطراف خود بهگونهاي است كه رفتار كوانتومي آنها بعد از مدتي طي فرايندي موسوم به ناهمدوسي كوانتومي (Quantum decoherence) از بين ميرود. حالت كوانتومي اين كيوبيتها بهشدت آسيبپذير و ناپايدار است و كوچكترين لرزش يا تغيير دما (اختلالاتي كه در زبان كوانتوم به آن «نويز» ميگويند) ميتواند آنها را قبل از انجام هرگونه محاسبهاي از حالت برهمنهي خارج كند.
به همين خاطر است كه محققان براي محافظت از كيوبيتها در مقابل اختلالات محيط بيروني، آنها را در يخچالهاي فوق سرد يا محفظههاي خلأ قرار ميدهند.
حالت كوانتومي كيوبيتها بهشدت ناپايدار است
اما با تمام اين تلاشها، نويز همچنان باعث بروز خطاهاي بسياري در محاسبات كوانتومي ميشود و تصحيح اين خطاها نيز كار بسيار دشواري است. از انديشه متخصصين گِرِگ كوپربرگ، رياضيدان دانشگاه كاليفرنيا، محاسبهي كوانتومي كه گوگل در اكتبر ۲۰۱۹ اعلام كرد به كمك كامپيوتر ۵۷ كيوبيتي تنها در سه دقيقه (بهجاي ۱۰ هزار سال با كامپيوتر معمولي!) انجام داده است، «۹۹ درصد نويز و تنها يك درصد سيگنال بوده است.»
كيوبيتهاي پايدار (كيوبيت منطقي) مقاومت بيشتري در برابر تأثيرات نويز نشان ميدهند اما ساخت هر يك كيوبيت منطقي به هزاران كيوبيت استاندارد نياز دارد كه بسيار زمانبر است. در حال حاضر محققان قادر به توليد ۱۲۸ كيوبيت بودهاند و سالها زمان لازم است تا اين تعداد به حدي برسد كه امنيت رمزارزها و ساير دادههاي رمزنگاريشده را بهطور جدي به خطر بيندازد. براي مثال در سال ۲۰۱۵، محققان تخمين زدند براي رمزگشايي از دادهاي با امنيت ۲۰۴۸، يك ميليارد كيوبيت لازم است.
تا آن روز هم رمزنگارها بدون شك به الگوريتمهاي رمزنگاري پساكوانتومي دست پيدا كردهاند كه در برابر رايانش كوانتومي مقاوم خواهد بود. اين الگوريتمها الزاما از روش جديدي براي رمزنگاري استفاده نميكنند، بلكه فقط كافي است از عددهاي بسيار بزرگتري استفاده كنند تا حتي محاسبات كوانتومي هم توان شكستن آنها را نداشته باشد.
از طرفي برخي محققان نويد اينترنت كوانتومي امن و هكناپذير را در چند سال آينده دادهاند كه قرار است به دغدغههاي امنيتي و حريم شخصي متخصصان اينترنت پايان بدهد. محققان دانشگاه دلفت در هلند در حال كار روي زيرساخت اينترنت كوانتومي هستند كه در آن ارتباطات بهصورت كيوبيت رمزنگاري، با فوتون درهمتنيده و سپس از ميان فيبرهاي نوري ردوبدل ميشود. در اين حالت رمزگشايي اين كيوبيتها بدون مختل كردن كل شبكه ممكن نيست؛ به اين معني كه اگر كسي تلاش كند شبكهي ارتباطي را هك يا استراق سمع كند، ارتباطات مختل و نامفهوم ميشود.
بدين ترتيب، رايانش كوانتومي و الگوريتم شور اگرچه براي رمزنگاريهايي كه از تابع دريچه استفاده ميكنند، تهديدي جدي به حساب ميآيند؛ اما بسيار بعيد است امنيت داده به اين زودي در آخرالزماني كوانتومي بهطور كامل از بين برود.
انديشه متخصصين شما متخصص اخبار تخصصي، علمي، تكنولوژيكي، فناوري مرجع متخصصين ايران دربارهي رايانش كوانتومي و تهديد آن براي امنيت دادههاي رمزنگاريشده و رمزارزها چيست؟ آيا توسعهي كيوبيتها سريعتر از توسعهي الگوريتمهاي رمزنگاري پساكوانتومي اتفاق خواهد افتاد؟
هم انديشي ها