Cryptography

導論篇

計算理論簡介

計算理論的歷史

可計算性

可計算性簡介

圖靈機

不可計算問題

遞歸可枚舉

不完備定理

複雜度

複雜度簡介

複雜度理論

NP-Complete

隨機複雜度

密碼學理論

趨近演算法

訊息

相關網站

參考文獻

最新修改

簡體版

English

Chapter 12 Cryptography

One way function f: 
1. f is 1-1 and x inΣ*,|x|^1/k ≦ |f(x)| ≦ |x|^k for some k
2. f in FP
3. f-1 !in FP

RSA的另兩個特性:
1. trapdoor function : 
    fRSA(x,e,p,c(p),q,c(q)) 有一定比例不是Undefine (是defined)
2. d(x) in P, f(d, fRSA(x, e)) = x

Class UP (unambiguous nondeterministic polynomial)
  x |{path | M(path, x) = “yes” }| ≦ 1

Theorem : UP = P iff there are no one way function

Signature : 
  S(x) = (x, D(d,x))

  A -- S(x) -- > B – encrypt D(d,x) -- > E(D(d,x)) = x

  B check is x = E(D(d,x)) ? 
  if “yes” then S(x) is send by A 
            otherwise S(x) may be a lie.

Commutative :
  E(e, D(d,x)) = D(d, E(e,x))

Theorem : RSA encryption system is commutative 
  D(d, E(e,x)) = (x^e)^d mod pq = (x^d)^e mod pq = E(e, D(d,x))

Interactive Proof System (A,B):

x  A    –- m[1],.. , m[2|x|^k-1] -- > B  x
        < -- m[2],.. , m[2|x|^k]    --     

    m[2i-1] = A(x, m[1], .. , m[2i-2])
m[2i]        = B(x,m[1],..,m[2i-1]) 
m[2|x|^k] in {“yes”, “no”}

    m[I] ≦ |x|^k

(A,B) decide L iff 
  if x in L  then P((A  ,B) accept x) ≧ 1-(2^-|x|)
  if x !in L then P((A’,B) accept x) ≦ 2^-|x| , for all A’≠A

Class IP : 
  x in IP => x decide by some interactive proof system (A,B)

NP  in IP
BPP in IP

Theorem : Graph Nonisomorphizm in IP
Proof :
     -- m[1] = (G,G’) -------------->
  A  <-- m[2i-1]=(G, Πi(Gi)) ------  B
 -- m[2i]= isIso(G, Πi(Gi)) --->

  Πi(Gi) : if b[i] = 1 then G else G’

  if (isIso(G,G’)) 
  then m[2] = .. = m[2|x|] = 1
  else if m[2] = b[1], .., m[2|x|] = b[|x|]
        then B accept it (return iso(G,G’))
        else B reject it (don’t believe iso(G,G’))

Facebook

Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-NonCommercial-ShareAlike 3.0 License