عدد $x$ای بیابید که $7x$ به پیمانهٔ ۱۶۰ همنهشت با ۱ باشد.

Question

اگر $ e=7 $ آنگاه مقدار $ d $ را طوری پیدا کنید که $de\overset{160}{\equiv}1$.

Comments

در سایت امکان اپلود انواع عکس و فایل وجود داره. از این امکانات استفاده کنید.

---

@fo-eng جملهٔ پرسشی‌تان کاری به الگوریتم RSA نداشت و بدون آوردن این الگوریتم پرسش‌تان معنا دارد. اگر از خود الگوریتم پرسش دارید، متن پرسش‌تان را طوری بنویسید که همان چیزی که می‌خواهید را بپرسد و اگر نه یافتن یک عدد که در برابری همنهشتی بالا صدق کند یک پرسش کامل و مستقل است. بعلاوه متن‌ها را تایپ کنید نه تصویر و اگر از کتابی چیزی را کپی می‌کنید باید به مشخصات کتاب اشاره کنید و بگوئید فلان چیز قسمت فلانِ فلان کتاب است که حق اثر اصلی رعایت شود.

Answer 1

بطور خلاصه روش کار برای تهیه کلیدهای عمومی و خصوصی به شرح زیر است:

1- دو عدد بزرگ (هر چه بزرگتر بهتر) اول به نام‌های p و q را انتخاب می‌کنیم، بهتر است این اعداد از لحاظ سایز نزدیک به یکدیگر باشند. مثلا $p=3, q=11$

2- عدد دیگری بنام n را معادل با حاصلضرب p در q تعریف می‌کنیم : $n = p q=3 \times 11=33$

3- عدد چهارم یعنی m را معادل حاصلضرب p-۱ در q-۱ تعریف می‌کنیم : $m = (p-۱)(q-۱)=2 \times 10=20$

4- عدد e را که از m کوچکتر است آنگونه پیدا می‌کنیم که بزرگترین مقسوم علیه مشترک این دو یک باشد به عبارتی نسبت به هم اول باشند.

5- عددی مانند d را پیدا کنید که باقی‌مانده حاصلضرب d در e تقسیم بر m مساوی عدد ۱ باشد، یعنی : d x e) mod m = ۱)

حال پس از طی این مراحل شما می‌توانید از e و n بعنوان کلید عمومی و از d و n بعنوان کلید اختصاصی استفاده کنید.

برای یافتن d و e بهتر است مرحله 4 و 5 را با هم درنظر بگیریم تا سریعتر به جواب برسیم: $$gcd(e,m)=gcd(e,2^2 \times 5)=1$$ $$d \times e ( mod m)= d \times e (mod 20)=1$$ ابتدا عددی را پیدا می کنیم که باقیمانده آن بر 20 عدد 1 شود، یعنی 21، پس داریم $d \times e=21$. از طرفی 21 را تجزیه می کنیم که می شود: $21=3 \times 7$، حال e را باید 3 یا 7 درنظر گرفت که نسبت به 20 اول باشد یعنی عامل 2 یا 5 نباشد، پس هر کدام از اعداد 3 یا 7 را می توان برابر با e درنطر گرفت چون هردو نسبت به 20 اولند. فرض کنید $d=7 \Longleftarrow e=3$

بنابراین کلید عمومی:$(n,e)=(33,3) $

کلید اختصاصی:$(n,d)=(33,7)$

Answer 2

اینکه $de \ \ mod \ \ 160 =1 $ یعنی باقیمانده تقسیم $ de $ بر 160 برابر 1 باشد پس در حالت کلی $ de $ به صورت $160k+1 $ خواهد بود

باید دقت کنیم عددی که بدست می آوریم مضرب $e=7 $ باشد مثلا اگر $k=1 $ عدد $161 $ را داریم که برابر است با $ 7 \times 23 $ و لذا قابل قبول است و $ d=23 $ می شود.

اما اگر $ k=2$ را قرار دهیم داریم $160 \times 2+1=321$ که بر 7 بخش پذیر نیست لذا قابل قبول نیست.

اینکه گفته شده $d< 160 $ و پس $de=7d < 7 \times 160$ پس مقادیر $ k $کمتر از $7$ خواهد بود چون $de=160k+1$

Answer 3

در مثال شما:$$p=17,q=11$$ $$n=pq=17 \times 11=187$$ $$m = (p-۱)(q-۱)=16 \times 10=160=2^5 \times 5$$ حال مراحل 4 و 5: $$gcd(e,m)=gcd(e,2^5 \times 5)=1$$ $$d \times e ( mod 160)= d \times e (mod 160)=1$$ پس باید:$d \times e=161=23 \times 7$ که 7 و 23 هر دو نسبت به 160 اولند زیرا عاملهای 2 و 5 ندارند پس:

$$d=7 \Longleftarrow e=23$$ یا $$d=23 \Longleftarrow e=7$$