و.. قضیه فرما..!!!

فرما در حاشیه  نسخه رونوشتش از  Diophantus' Arithmetica می نویسد }

برای تقسیم کردن یک عدد مکعب کامل به دو مکعب دیگر ، توان 4  و در حالت کلی هر توانی از هر عددی به دو توان هم جنس همانطور که ذکر شد حالت دومی نیز ممکن است ، و من مطمئنا یک اثبات تحسین بر انگیز برای آن پیدا کرده ام ، اما حاشیه کتاب برای نوشتن آن بسیار باریک است!!!!!!
پیر فرما

در ابتدای این سلسله مقالات به بیان مفهوم کلید عمومی و شیوه رمز نگاری نا متقارن پرداختیم سپس در ادامه روش های تایید هویت  که مکمل این شیوه است مورد بررسی قرار گرفت و پس از آن از ایده اولیه الگوریتم آر اس ای  -که نوعی روش به رمز در آوردن اطلاعات مبتنی بر شیوه کلید عمومی است- صحبت شد و حالا در ادامه  مثال کاملی را برای بیان الگوریتم RSA مطرح می کنیم .در اینجا سعی شده تا از اعداد اول بسیار کوچکی استفاده شود تا ادامه روند محاسبات ساده باشد اما باید توجه داشت که در کاربرد واقعی روش RSA  این اعداد باید بسیار بزرگ ،حداقل دارای 100 رقم ، انتخاب می شود:

در طول این مثال فرض کنید شخص A می خواهد یک کلید عمومی برای خود بسازد و  شخص B می خواهد با استفاده از این کلید عمومی برای A پیغامی بفرستد. فرض می کنیم که A و B بر سر روشی برای برمز در آوردن متن بصورت اعداد توافق کرده اند .بنابراین این گام ها باید پیموده شود :

1. ابتدا شخص A دو عدد اول انتخاب می کند . ما از اعداد p=23 و q=41 استفاده می کنیم .

2. شخص A دو عدد p و q را در هم ضرب میکند تا به N=p.q=(23)(41)=934 برسد . 934 کلید عمومی او است ، که آنرا به نفر B می دهد ( و همچنین به باقی افرادی در جهان که متمایل باشد )

3. شخص A همچنین عدد دیگری چون e را که نسبت به (M=(p-1)(q-1 اول باشد. یعنی بزرگترین مقسوم علیه مشترک آنها یک باشد یا p-1)(q-1),e)=1)). در این مورد خاص M=(p-1)(q-1)=(22)(40)=880 بنابراین e=7 مناسب است. e نیز قسمتی از کلید عمومی است و باید علاوه بر p.q ، e نیز به شخص B گفته شود......

و.. قضیه فرما..!!!( رمزنگاری)

{فرما در حاشیه  نسخه رونوشتش از  Diophantus' Arithmetica می نویسد }

برای تقسیم کردن یک عدد مکعب کامل به دو مکعب دیگر ، توان 4  و در حالت کلی هر توانی از هر عددی به دو توان هم جنس همانطور که ذکر شد حالت دومی نیز ممکن است ، و من مطمئنا یک اثبات تحسین بر انگیز برای آن پیدا کرده ام ، اما حاشیه کتاب برای نوشتن آن بسیار باریک است!!!!!!
پیر فرما

در ابتدای این سلسله مقالات به بیان مفهوم کلید عمومی و شیوه رمز نگاری نا متقارن پرداختیم سپس در ادامه روش های تایید هویت  که مکمل این شیوه است مورد بررسی قرار گرفت و پس از آن از ایده اولیه الگوریتم آر اس ای  -که نوعی روش به رمز در آوردن اطلاعات مبتنی بر شیوه کلید عمومی است- صحبت شد و حالا در ادامه  مثال کاملی را برای بیان الگوریتم RSA مطرح می کنیم .در اینجا سعی شده تا از اعداد اول بسیار کوچکی استفاده شود تا ادامه روند محاسبات ساده باشد اما باید توجه داشت که در کاربرد واقعی روش RSA  این اعداد باید بسیار بزرگ ،حداقل دارای 100 رقم ، انتخاب می شود:

در طول این مثال فرض کنید شخص A می خواهد یک کلید عمومی برای خود بسازد و  شخص B می خواهد با استفاده از این کلید عمومی برای A پیغامی بفرستد. فرض می کنیم که A و B بر سر روشی برای برمز در آوردن متن بصورت اعداد توافق کرده اند .بنابراین این گام ها باید پیموده شود :

1. ابتدا شخص A دو عدد اول انتخاب می کند . ما از اعداد p=23 و q=41 استفاده می کنیم .

2. شخص A دو عدد p و q را در هم ضرب میکند تا به N=p.q=(23)(41)=934 برسد . 934 کلید عمومی او است ، که آنرا به نفر B می دهد ( و همچنین به باقی افرادی در جهان که متمایل باشد )

3. شخص A همچنین عدد دیگری چون e را که نسبت به (M=(p-1)(q-1 اول باشد. یعنی بزرگترین مقسوم علیه مشترک آنها یک باشد یا p-1)(q-1),e)=1)). در این مورد خاص M=(p-1)(q-1)=(22)(40)=880 بنابراین e=7 مناسب است. e نیز قسمتی از کلید عمومی است و باید علاوه بر p.q ، e نیز به شخص B گفته شود.

4. حالا B اطلاعات کافی برای برمز در آوردن یک پیغام برای A را دارد . فرض کنید که در این مثال پیغامی مورد نظر عدد P=35 باشد .

5. شخص B  مقدار(C=P^e(mod N)=35⁷(mod 943 را حساب می کند.

۶.535⁷=6433929687 و ۵64339296875(mod 943)=545 

عدد  545در واقع پیغام رمزگذاری شده ای است که B به A می فرستد.

7. حالا A می خواهد 545 را رمزگشایی کند برای این کار او عددی را چون d نیاز دارد طوری که((ed=1(mod (p-1)(q-1 ، یا در این مثال(7d=1(mod 880جواب فرد A برای d عدد 503 خواهد بود ، زیرا داریم(7x503=3521=(4x(880)+1)(mod 800.

8. برای پیدا کردن متن رمزگشایی شده ، A مجبور است

(C^d (mod N)=545⁵⁰³ (mod 943

را حساب کند. در ابتدا به نظر می آید که این کار بسیار دشوار است اما توجه کنید

503 = 256+128+64+32+16+4+2+1

(که در واقع بسط دودویی عدد 503 است ) بنابر این خواهیم داشت

545⁵⁰³ = 545^{256+128+64+32+16+4+2+1} = 545²⁵⁶545¹²⁸ … 545¹

اما از آنجا که ما تنها علاقمند به پیدا کردن باقی مانده به پیمانه 943 هستیم ، می توانیم با محاسبه باقیمانده تمام عامل های ضربی در این پیمانه به مقصودمان برسیم و این کار را می توانیم با به توان 2 رساندن های متوالی عدد 545 انجام دهیم زیرا تمام توان های عامل های ضربی ، مضربی از 2 هستند.
به عنوان مثال برای اینکه به باقی مانده  توان 4 ام عدد 545 برسیم داریم :

n = 0 => d = 1 / 5 (غ.ق.ق)
n = 1 => d = 109 / 5 (غ.ق.ق)
n = 2 => d = 217 / 5 (غ.ق.ق)
n = 3 => d = 325 / 5 = 65 (ق.ق)

رمزگذاری متن(عدد) p=6:

C = P^e % n
  = 6⁵ % 133
  = 7776 % 133
  = 62

رمزگشایی متن رمز گذاری شده C=62:

P = C^d % n
  = 62⁶⁵ % 133
  = 62 * 62⁶⁴ % 133
  = 62 * (62²)³² % 133
  = 62 * 3844³² % 133
  = 62 * (3844 % 133)³² % 133
  = 62 * 120³² % 133

با ادامه کاهش توان به روش فوق که توان عبارت 6265  به 12032 کاهش داد و در واقع همان روش فوق یعنی تجزیه توان به جمعوند هایی که توان های 2 هستند ولی این بار در جهت عکس حرکت می کنیم یعنی از جمعوند آخری داریم :

= 62 * 36¹⁶ % 133
  = 62 * 99⁸ % 133
  = 62 * 92⁴ % 133
  = 62 * 85² % 133
  = 62 * 43 % 133
  = 2666 % 133
  = 6

که با متن اولیه p=6 مطابق است . بنابراین الگوریتم RSA درست کار می کند !

تمرین

حالا برای تمرین فرض کنید شما شخص ، A  هستید و عدد های  p=97 و q=173 را بعنوان عدد های اول و همچنین عدد e را 5 انتخاب کرده اید . بنابراین شما عدد N=16781 ( که همان حاصل p.q ) و e=5 را در اختیار فرد B می گذارید .
او متنی را(یک عدد) برای شما رمزگذاری  می کند و برای شما عدد رمزگذاری شده 5347 را می فرستد . خوب حالا ببینید می توانید عدد اصلی را رمز گشایی کنید .

کلید واژه ها :الگوریتم رمزنگاری آر اس ای  RSA Encryption Algorithm  متن رمزگشایی شده (متن اصلی) Plaintext  متن رمزگذاری شده Ciphertext

منبع:

amath.blogfa.com