クラシックパスワード

暗号学の段階区分
暗号学の発展はアルゴリズムと鍵に対する秘密保持の程度によって大きく以下の3つの段階に分けることができる.

古典暗号段階(1949年前)はこの段階でアルゴリズムと鍵が秘密にされており、鍵空間が小さく、情報の安全性は主に暗号化と復号アルゴリズムに対する秘密に依存している.

対称暗号段階(1949-1975年)はその後、現代暗号学の段階に入り、古典暗号段階との主な違いは、この段階の暗号化と復号アルゴリズムが秘密保持を必要とせず、情報の安全性は主に鍵の秘密保持に依存することである.解決すべき主な問題は、信頼できないチャネルにおける鍵伝送の問題である.

公開鍵暗号化フェーズ(1976年-現在)公開鍵暗号化フェーズでは、暗号化鍵(公開鍵)を公開することができ、復号鍵(秘密鍵)のみを秘密にすることができ、いくつかの数学的難題に基づいて公開鍵を通じて秘密鍵を発売することが困難であることを保証する.

数学の知識

の除去と約簡略

同余

素数の相関特性の各正の整数は、一連の素数の積に分解することができ、この分解は一意である.

n=pe11+pe22...pemmei>0,i=1,2,....mn=p1e1+p2e2...pmemei>0,i=1,2,....m

ユークリッドアルゴリズムと拡張ユークリッドアルゴリズムユークリッドアルゴリズム(転がり相除法)ユークリッドアルゴリズムを学ぶ際にいくつかの困難に遭遇したことを覚えておきましょう.まず、任意のxとyが同時に0でない整数に対して、xとyの最大公因子(x,y)はax+byax+byで表される最小整数である.ユークリッドアルゴリズムを拡張することは、このaとbを求めるために使用されます.次の図は計算方法の導出過程である:上の導出によって以下のような式を書くことができる:

[011−qn][011−qn−1]...[011−q1][xy]=[gcd(x,y)0][011−qn][011−qn−1]...[011−q1][xy]=[gcd(x,y)0]
マトリクスを乗算するとa,bが求められ,解の方向によって再帰と非再帰のアルゴリズムが得られ,マトリクスは左から右へ再帰アルゴリズム(左から右へも非再帰アルゴリズムと書くことができるが,qnqnを1つの配列で記録する必要がある),マトリクスは右から左へアルゴリズムは非再帰アルゴリズムである.再帰アルゴリズムの実装:

void exgcd(int a,int b,int &x,int &y)
{
    if(b==0)
    {
        x=1;
        y=0;
        return;
    }
    exgcd(b,a%b,x,y);
    int t=x;
    x=y;
    y=t-a/b*y;
    return;
}

非再帰アルゴリズムの実装

void exgcd(int m,int n,int &x,int &y)
{
    int r=1;
    vector qList;
    while (r!=0){          //    q   vector          r=m%n;
        int q=m/n;
        qList.push_back(q);
        m=n;
        n=r;
    }
    int listSize=qList.size();
    x=0;
    y=1;
    for(int i=listSize-2;i>=0;--i){ //  x，y         int tempX=x;
        x=y;
        y=tempX-y*qList[i];
    }
}

非再帰アルゴリズム2実装:

void exgcd(int m,int n,int &x,int &y)
{
    int x1,y1,x0,y0;
    x0=1; y0=0;
    x1=0; y1=1;
    x=0; y=1;
    int r=m%n;
    int q=(m-r)/n;
    while(r)
    {
        x=x0-q*x1; y=y0-q*y1;
        x0=x1; y0=y1;
        x1=x; y1=y;
        m=n; n=r; r=m%n;
        q=(m-r)/n;
    }
}

乗算逆元定義:nモードmの乗算逆t記(n−1%mn−1%m)はnt%m=1乗算逆の存在条件を満たす:(n,m)=1簡単証明:nt%m=1=>nt=km+1(km+1,km)=1=>(km+1,m)=1=>(nt,m)=1(n*t,m)=1=>(n,m)=1=>(n,m)=1得証計算乗算逆の方法:拡張ユークリッドアルゴリズムを用いてan+bm=1を求めると、aはその乗算逆である.

クラシック暗号学-パスワードの代わりに
暗号学では情報を処理する主な方法は2つのシフトと代替があり、その名の通りシフトは元の明文文字の順序を乱すことであり、代替は一定の法則に従って明文文字を他の文字に置き換えることである.処理方法によって、具体的な分類は下図のように(盗難の授業ppt上の図(
Caesarパスワード
Caesarパスワードは非常に簡単で、一般的な式は以下の通りです.
y=f(x)=(x+k)%26(暗号化)x=f(y)=(y−k)%26(復号化)y=f(x)=(x+k)%26(暗号化)x=f(y)=(y−k)%26(復号化)
Caesar暗号の暗号鍵kと復号鍵は同じであり,同時に鍵空間の大きさは25であり,kの数値を試行し続けることで鍵を非常に容易に得ることができる.
シミュレーションパスワード
Caesar暗号の鍵空間が小さいため,パラメータを増やして鍵空間サイズを上げることでアフィニティ暗号が得られる.
y=Ea,b(x)=(ax+b)%26(暗号化)y=Da,b=(a−1 y−a−1 b)%26(復号化)y=Ea,b(x)=(ax+b)%26(暗号化)y=Da,b=(a−1 y−a−1 b)%26(復号化)
解析により,その鍵空間サイズは311であり,その計算式は12*26−1であることが分かった.12はaの可能性を表し、a型26の乗算逆は必ず存在しなければならないので、その値はφ(26),26はbの可能性であり,減算はa=1,b=0の特殊な場合である.シミュレーションパスワードの鍵長は拡大されているが依然として限られていると同時に、本質的にはパスワードの代わりに単表であり、暗号文には明文中の文字の統計法則が残っており、解読されやすい.
Vignereパスワード
Vignereのマルチテーブルはパスワードの代わりに最も有名で最も簡単であり、本質的には複数のCaesarパスワードの組み合わせにすぎず、1ビットごとにCaesarパスワードの鍵を交換し、終了するまでループを開始する.その鍵シーケンスは、K=k 0,K 1,K 2,...Km−1 K 0,K 1,K 2,...Km−1,K 2,...Km−1と表され、CaesarパスワードがVignereパスワードの鍵長さが1の場合の特殊な状況であることがわかる.具体的な復号式は次のとおりです.
yi=(xi+ki%m)%26(暗号化)xi=(yi−ki%m)%26(復号化)yi=(xi+ki%m)%26(暗号化)xi=(yi−ki%m)%26(復号化)
Vignere暗号の鍵空間は26 m 26 mであり,鍵空間は非常に大きいといえるが,多くの周波数分布の特徴が残っているため,Kasiski試験法と重ね合わせ指数攻撃により鍵があまり長くない場合に比較的簡単に解読でき,暗号に代わる複数のテーブルの攻撃方式を次回に書くことができる.
OTPパスワード(一次一密パスワード)
アルゴリズム原理:暗号化された鍵は明文と同じ長さであり、鍵自体は一度しか使用されない.具体的な暗号化方式は、任意にVignereパスワードであってもよいし、Vernamパスワードであってもよい.一度に1つの暗号は理論的に情報の完全な安全を保証した.いずれの意味のある明文も1つの唯一の鍵になるからだ.攻撃者が窮挙攻撃を採用すれば、多くの意味のある明文が得られ、攻撃者はどれが正しいか判断できない.欠点:大規模なランダム鍵の生成は非常に困難であり、同時に鍵の配布と保存がさらに面倒である.
クラシックパスワード-シフトパスワード
シフトパスワードはその名の通り、明文中のアルファベットを変更せずに明文中のアルファベットの順序だけを変更することであり、一般的な方法は列シフト暗号化があり、具体的な方法は下図に示す通りである.
復号方式は暗号化方式と似ている.