به محفل ریاضی ایرانیان خوش آمدید! لطفا برای استفاده از تمامی امکانات عضو شوید
سایت پرسش و پاسخ ریاضی
+1 امتیاز
558 بازدید
در دبیرستان و دانشگاه توسط fo-eng
ویرایش شده توسط fardina

اگر $ e=7 $ آنگاه مقدار $ d $ را طوری پیدا کنید که $ de \ \ mod\ \ 160=1 $

enter image description here

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

3 پاسخ

+2 امتیاز
توسط yedost

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

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)$

+1 امتیاز
توسط erfanm

اینکه $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$

+1 امتیاز
توسط yedost

در مثال شما:$$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$$

حمایت مالی


کانال تلگرام محفل ریاضی
امروز : تاریخ شمسی اینجا نمایش داده می‌شود
...