内容が複雑なのでWikiも引用しながら解説します。
####0.はじめに
デジタル署名（デジタルしょめい）とは、書面上の手書き署名のセキュリティ特性を模倣するために用いられる公開鍵暗号技術の一種である。
今回取り上げるのはRSAデジタル著名とゆうものです。
本書とは説明や、例が長く読みづらく感じたのでWikiからの引用で説明します。
#####1.RSA暗号とは
ロナルド・リベスト、アディ・シャミア、レオナルド・エーデルマン
この三人のイニシャルをとってRSAとゆう名前になっています。
RSA暗号の原理は フェルマーの小定理 + 中国人剰余定理
RSA暗号は鍵生成、暗号化、復号の三つのアルゴリズムを用います。
数学的な話になってくるとオイラーのトーシェント関数や拡張されたユークリッド互除法や剰余計算など複雑な計算が必要になってくるのである程度を難しいですが説明いたします。
RSA暗号（RSAあんごう）とは、桁数が大きい合成数の素因数分解問題が困難であることを安全性の根拠とした公開鍵暗号の一つである。 暗号とデジタル署名を実現できる方式として最初に公開されたものである。
桁数の大きい合成数の素因数分解が困難とゆう性質を利用した暗号化なので、素因数分解ができる数値を全部公開してしまうと、簡単に解かれ安全性がなくなるので、秘密にする数値、公開する数値などを用いて、アルゴリズムが公開されています。
#####2.鍵生成、暗号化、、復号の三つのアルゴリズム
鍵生成の条件として、１セットの南京錠と鍵をそして署名を入れる箱を用意します。南京錠は専用の鍵がないと開けれません。
鍵は公開します。誰でも開けれるのです。その代わりに南京錠は本人しかロックできないようにします。ここが署名のポイントになります。
鍵を公開しないとロックだけして鍵を渡さないとゆうパターンがあるので鍵は公開します。
本人以外がロックできるようにすると。永遠に開けられない南京錠になる可能性もできますよね。
このアルゴリズムを数値化するとデジタル署名として利用ができます
復号は、鍵を使い南京錠を開けるとゆう過程ですね。公開された鍵を使って開けます。
ここからは計算
#####鍵生成
1素数p,qを選ぶ。
2n=pq || f = (p-1)(q-1) を計算
3素数eを選ぶ
4d = 1/e mod(f)
(e,n)が公開鍵 (d,n)が復号鍵になります
#####暗号化
１文をn以下の数Mに変換（公開）
２C=M^e mod(n)で暗号Cを作成
#####復号化
1M = c^d mod(n)でもとの数Mに変換
2数Mを分に変換する
#####例
素数p、qを選ぶp = 239 , q = 547 ： 選定
n=pq = 130733,f = (p-1)(q-1) = 129948
暗号鍵を選定する e = 43291
(e,n) = (43291,130733)を公開
復号鍵(秘密鍵、d)の作成
d = 1/e = 1/43291 = 105691 mod f
(f,e)=(129948,43291)にユークリッド互除法
129948 = 3×43291 + 75
43291 = 577×75 + 16
75 = 4×16 + 11
16 = 1×11 + 5 5 = 16 - 1×11
11 = 2 ×5 + 1 1 = 11 - 2 ×5
互除法の結果(逆順)からe,fの一次式を作成
1 = 11 - 2 ×5 = 11 – 2 ×(16 - 1×11)
= 3×11 - 2 ×16 = 3×(75 - 4×16) - 2 ×16
= 3×75 - 14 ×16
= 3×75 - 14 ×(43291 – 577 ×75)
= 8081×75 - 14 ×43291
= 8081×(f - 3×e) - 14 ×e
= 8081×f - 24257×e
1 = 8081×f - 24257×e のmod f の計算
1 = 8081×f - 24257×e mod f
= -24257×e mod f
= (f – 24257)×e mod f
= (129948 – 24257)×e mod 129948
= 105691×e mod 129948
従って複合鍵(d)は
d =1/e = 105691 mod 129948
#####3.最後に
このようにしてRSA暗号化は成り立っています。安全性の確保は前述した通り素因数分解の困難さです。現在は2020年2月に250桁の素因数分解が世界記録ですのでRSA 鍵を作るときはこの桁数以上に大きな桁で鍵を生成しないといけないですね。
詳しく知りたい方はRSA暗号の数理など検索していただけれなと思います。