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

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 and 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가 common divisor가 1을 제외하고 없을때, a와 b는 relatively prime이다

GCD

  • greatest common divisor

  • by comparing their prime factorizations & using the least common powers(가장 큰 공약수) -> we can determine the 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)

    • 예시1

    • 예시 2

Modular Arithmetic

나머지 연산

  • 용어정리

    • congruence
      modular 연산후 같은 remainder 가질때
      ex) 100 mod 11 = 34 mod 11 = 1
    • Residue
      a mod n = b 혹은 a = qn + b 일때 b
      보통 가장 작은 정수를 고름
  • ⚠️Properties⚠️
    a = b (mod n) and c = d (mod n) 일때,

    • a + c = b + d (mod n)
    • ac = bd (mod n)
    • a = b(mod n) ak=bk\rightarrow a^k = b^k(mod n)
    • a + kn = b(mod n)
  • relatively prime한 두 수 a, b가 있을때
    aai=1(modb)aa^i = 1(mod b)

    • aia^i는 Extended Euclidean algorithm으로 계산가능

Euler Totient Fucntion

  • residues

    • complete residue : 모든 residue
    • reduced residue : n과 relative prime인 residue
      • 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)
    reduced set of residues의 원소 갯수
    ex) φ(10)=4\varphi(10) = 4

    • ex) φ(37)\varphi(37) = 37-1 = 36
      φ(11)\varphi(11) = 11-1 = 10
      φ(21)\varphi(21) = (3-1)*(7-1)=2*6=12
      φ(10)\varphi(10) = (2-1)*(5-1)=1*4=4
  • Fermat's Little Theorem
    ap1=1a^{p-1}=1

    • ex
      464^6mod 7 = 1
      192219^{22}mod 23 = 1

      Fermat's Little Theorem 응용
      매우 큰 수 p에 대해, ap1=1a^{p-1}=1

    • ex
      4374^{37}mod 7 = 46×6+14^{6\times 6+1}mod 7 = 16×1^6 \times 4 mod 7 = 4
      1922×2+119^{22\times 2+1} mod 23 = (1922)2×(19^{22})^2\times

  • Euler's Theorem
    φ(n)\varphi (n)이 Euler's Totient function 이고,
    gcd(a,n) = 1 이면
    aφ(n)=1a^{\varphi(n)}=1

    • ex
      2512025^{120} mod 143 = 25(111)(131)25^{(11-1)(13-1)} mod 11 X 13 = 1
      196019^{60} mod 77 = 19(71)(111)19^{(7-1)(11-1)} mod 7 X 11 = 1
  • Euler's Theorem 응용
    aφ(n)a^{\varphi(n)} mod n = 1 이니까

    • aφ(n)×k+1a^{\varphi(n)\times k + 1} mod n = a
    • aφ(n)+1a^{\varphi(n) + 1} mod n = a
    • ex
      25120125^{1201} mod 143 = 25120×10+125^{120\times 10 + 1} mod 11 X 13 = 25
      1948119^{481} mod 77 = 1960×8+119^{60\times 8 + 1} mod 7 X 11 = 19

좋은 웹페이지 즐겨찾기