6. Basic Mathmatics for Cryptography - Euclid's Algorithm & Fermat's Little Theorem & Euler's Theorem

5784 ワード
情報セキュリティ CS SSU 現代暗号学 テキストリンク

INDEX

  • part1
  • greates common divisor
  • (extended) Euclid's Algorithm
  • Modular Arithmetic
  • Euler's Totient Function
  • Fermat's Theorem
  • Euler's Theorem
  • part2
  • randomness
  • true random nubmer
  • pseudo-random number
  • cryptographic pseudo-random number

    • prime number


    prime number


  • prime number=素数=only have divisors of 1とself
  • cannot be written as a product of other number
  • 1 is prime, but is generally not of interest

  • Prime Factorization
    : All numbers can be expressed as a unique products of primes. (すべての数字はprime numの積で表すことができます)
    n = a X b X c
  • ex) 10 = 25 , 20 = 22*5
  • factoring a number is relatively hard!
  • relatively prime numbers
  • a,bが1を除く共通因子がない場合、a,bは相対素数
    • である.

    GCD


  • greatest common divisor

  • それらの素数分解を比較&最小べき乗(最大公約数)->GCDを決定できる
  • ex) gcd(273, 399)
    273 = 3*7*13, 399 = 3*7*19.
    gcd(273, 399) = 3*7=21

  • Euclid Algorithm
    gcdが入手できます!
  • 首都コード
    • def Euclid_GCD(a,b) :
# Assume a and b are nonnegative integers
if (b==0) :
  gcd(a,b) = a # stopping condition
else 
  gcd(a,b) = gcd(b, a%b) # recursive step
  • 例
    a = 54, b = 30.
    gcd(54, 30) = gcd(30, 54%30) = gcd(30, 24)
    gcd(30, 24) = gcd(24, 30%24) = gcd(24, 6)
    gcd(24, 6) = gcd(6, 24%6) = gcd(6,0)
    gcd(6,0) = 6
    =>>GCDは6!

  • Extended Euclidean Algorithm
    a×x+b×y=gcd(a,b)a\times x +b\times y = gcd(a,b)a×x+b×y=gcd(a,b)
    整数a,bが与えられると,中間過程のxとyも知ることができる.

  • 例1


  • 例2

    • Modular Arithmetic


    ざんりゅうえんざん

  • クリーンアップ用語
  • congruence
    模演算後の残存値が等しい場合
    ex) 100 mod 11 = 34 mod 11 = 1
  • Residue
    a mod n=bまたはa=qn+bの場合b
    通常の最小整数は
    • です.

  • ⚠️Properties⚠️
    a=b(modn)およびc=d(modn)の場合、
  • a + c = b + d (mod n)
  • ac = bd (mod n)
  • a = b(mod n) →ak=bk\rightarrow a^k = b^k→ak=bk(mod n)
  • a + kn = b(mod n)

  • 2つの相対素数a,bがある場合
    aai=1(modb)aa^i=1(modb)aai=1(modb)のaia^iaiが存在する.
  • aia^iaiは拡張Euclideanアルゴリズムであり、
    • を計算することができる.

    • Euler Totient Fucntion


  • residues
  • 完全残渣:全残渣
  • 還元残渣:n及び相対素残渣
  • ex)n=10の場合
    complete set of residues = {0, 1, 2, 3, 4, 5, 6,7, 8, 9}
    reduced set of residues = {1, 3, 7, 9}

  • Euler Totient Function φ(n)\varphi (n)φ(n)
    減少した残留物の元素数
    ex) φ(10)=4\varphi(10) = 4φ(10)=4 (1, 3, 7, 9)
    ->n=pq,p,qがprimeの場合,n未満のnに対して相対primeの正数を求めることができる.
    pは素数->φ(p)=p−1\varphi(p) =p -1φ(p)=p−1
    p,qはprime->φ(pq)=(p−1)×(q−1)\varphi(pq)=(p-1)\times (q-1)φ(pq)=(p−1)×(q−1)
  • ex) φ(37)\varphi(37)φ(37) = 37-1 = 36
    φ(11)\varphi(11)φ(11) = 11-1 = 10
    φ(21)\varphi(21)φ(21) = (3-1)*(7-1)=2*6=12
    φ(10)\varphi(10)φ(10) = (2-1)*(5-1)=1*4=4

  • Fermat's Little Theorem
    ap−1=1a^{p-1}=1ap−1=1(mod ppp)
    where ppp is prime and gcd(a, p) = 1
    (pはPrime,a,pはPrime)

  • ex
    464^646mod 7 = 1
    192219^{22}1922mod 23 = 1
    Fermat's Little Theoryアプリケーション
    非常に大きな数pに対してapは-1=1 a^{p-1}=1 apは1=1(modppp)ですか?
    - apa^pap mod p=ap=ap=a
    - a(p−1)×k+1a^{(p-1)\times k+1}a(p−1)×k+1mod ppp = a

  • ex
    4374^{37}437mod 7 = 46×6+14^{6\times 6+1}46×6+1mod 7 = 16×1^6\times16× 4 mod 7 = 4
    1922×2+119^{22\times 2+1}1922×2+1 mod 23 = (1922)2×(19^{22})^2\times(1922)2× mod 23 = 19
    89100×10+189^{100\times10 + 1}89100×10+1 mod 101 = (89100)10×(89^{100})^{10}\times(89100)10×89 mod 101 = 89

  • Euler's Theorem
    φ(n)\varphi (n)φ(n)はEulerのTotiner関数で、
    gcd(a,n)=1の場合
    aφ(n)=1a^{\varphi(n)}=1aφ(n)=1(modnn).
  • ex
    2512025^{120}25120 mod 143 = 25(11−1)(13−1)25^{(11-1)(13-1)}25(11−1)(13−1) mod 11 X 13 = 1
    196019^{60}1960 mod 77 = 19(7−1)(11−1)19^{(7-1)(11-1)}19(7−1)(11−1) mod 7 X 11 = 1

  • Euler's Theoremアプリケーション
    aφ(n)a^{\varphi(n)}aφ(n)mod n=1
  • aφ(n)×k+1a^{\varphi(n)\times k + 1}aφ(n)×k+1 mod n = a
  • aφ(n)+1a^{\varphi(n) + 1}aφ(n)+1 mod n = a
  • ex
    25120125^{1201}251201 mod 143 = 25120×10+125^{120\times 10 + 1}25120×10+1 mod 11 X 13 = 25
    1948119^{481}19481 mod 77 = 1960×8+119^{60\times 8 + 1}1960×8+1 mod 7 X 11 = 19
    • J-Query数値処理方法
    スタック(Python付き)