教甄◆資訊科技概論專業(電腦科)題庫下載題庫

公鑰與私鑰的產生[編輯]

假設Alice想要通過一個不可靠的媒體接收Bob的一條私人訊息。她可以用以下的方式來產生一個公鑰和一個私鑰：

隨意選擇兩個大的質數{displaystyle p}和{displaystyle q}，{displaystyle p}不等於{displaystyle q}，計算{displaystyle N=pq}。根據歐拉函數，求得{displaystyle r=varphi (N)=varphi (p)times varphi (q)=(p-1)(q-1)}選擇一個小於{displaystyle r}的整數{displaystyle e}，使{displaystyle e}與{displaystyle r}互質。並求得{displaystyle e}關於{displaystyle r}的模反元素，命名為{displaystyle d}（求{displaystyle d}令{displaystyle edequiv 1{pmod {r}}}）。（模反元素存在，若且唯若{displaystyle e}...
查看完整內容

公鑰與私鑰的產生[編輯]

假設Alice想要通過一個不可靠的媒體接收Bob的一條私人訊息。她可以用以下的方式來產生一個公鑰和一個私鑰：

1. 隨意選擇兩個大的質數{displaystyle p}和{displaystyle q}，{displaystyle p}不等於{displaystyle q}，計算{displaystyle N=pq}。
2. 根據歐拉函數，求得{displaystyle r=varphi (N)=varphi (p)times varphi (q)=(p-1)(q-1)}
3. 選擇一個小於{displaystyle r}的整數{displaystyle e}，使{displaystyle e}與{displaystyle r}互質。並求得{displaystyle e}關於{displaystyle r}的模反元素，命名為{displaystyle d}（求{displaystyle d}令{displaystyle edequiv 1{pmod {r}}}）。（模反元素存在，若且唯若{displaystyle e}與{displaystyle r}互質）
4. 將{displaystyle p}和{displaystyle q}的記錄銷毀。

{displaystyle (N,e)}是公鑰，{displaystyle (N,d)}是私鑰。Alice將她的公鑰{displaystyle (N,e)}傳給Bob，而將她的私鑰{displaystyle (N,d)}藏起來。

p=43 q=59 N=pq=2537

r=(p-1)(q-1)=2436

e = 13

求e的模反元素 d  -> 將937代入測試 13 *937  = 12181

12181 mod 2436 = 1