PromleeBlog
sitemap
aboutMe

posting thumbnail
서명 스키마
Signature Schemes

📅
🚀 RSA 서명
✅ 키 생성
✅ 서명
✅ 검증
✅ 정확성
🚀 RSA 패딩: 확률론적 서명 표준
🚀 ElGamal 서명
✅ 키 생성
✅ 서명
✅ 검증
✅ 정확성
✅ 보안성
🚀 DSA 서명
✅ 키 생성
✅ 서명
✅ 검증
✅ 정확성
🚀

RSA 서명 (RSA Signature) 🔗

✅

키 생성 (RSA) 🔗

  1. 두 소수 p,qp, q를 무작위로 선택, N=pqN = pq로 설정
  2. 무작위 공개 지수 e∈Zϕ(N)∗e \in \mathbb{Z}^*_{\phi(N)}를 선택
  3. d⋅e≡1(modϕ(N))d \cdot e \equiv 1 \pmod{\phi(N)}를 만족하는 dd를 계산
  4. 공개 키 pk=(N,e)pk = (N, e), 개인 키 sk=dsk = d를 반환
✅

서명 (RSA) 🔗

메시지 MM에 대해 s=Md(modN)s = M^d \pmod{N}을 계산하여 서명 σ=(M,s)\sigma =(M, s)를 생성
✅

검증 (RSA) 🔗

σ=(M,s)\sigma = (M, s)가 주어졌을 때, se=?M (mod N)s^e \stackrel{?}{=} M \ (\text{mod} \ N)을 확인한다. 이 조건이 성립하면 1을 반환하고, 그렇지 않으면 0을 반환한다.
✅

정확성 (RSA) 🔗

se=(Md)e=Med=M1+kϕ(N)=M (mod N)s^e = (M^d)^e = M^{ed} = M^{1 + k\phi(N)} = M \ (\text{mod} \ N)이 오일러 정리에 의해 성립한다.
🚀

RSA 패딩: 확률론적 서명 표준 (RSA Padding: Probabilistic Signature Standard) 🔗

➡️

정리 (RSA PSS) 🔗

🚀

ElGamal 서명 (ElGamal Signature) 🔗

✅

키 생성 (ElGamal) 🔗

  1. 큰 소수 pp 와 Zp∗\mathbb{Z}_p^*의 큰 subgroup 생성자 gg를 선택
  2. 임의의 정수 x∈{2,3,…,p−2}x \in \{2, 3, \ldots, p-2\}를 선택
  3. X=gx(modp)X = g^x \pmod{p}를 계산
  4. 공개 키 pk=(p,g,X)pk = (p, g, X), 개인 키 sk=xsk = x를 반환
✅

서명 (ElGamal Signature) 🔗

✅

검증 (ElGamal Signature Verification) 🔗

✅

정확성 (ElGamal Signature correctness) 🔗

t=Xr⋅rs=(gx)r⋅(gk)s=(gx)⋅(gk)(M−rx)k−1=gxr+M−rx=gM (mod p)t = X^r \cdot r^s = (g^x)^r \cdot (g^k)^s \\= (g^x) \cdot (g^k)^{(M-rx)k^{-1}} \\= g^{xr+M-rx} \\= g^M \ (\text{mod} \ p)
✅

보안성 (ElGamal Signature Security) 🔗

⇒ 그러면 t=Xr⋅rs (mod p)t = X^r \cdot r^s \ (\text{mod} \ p)이 성립하며 t=gM (mod p)t = g^M \ (\text{mod} \ p)이므로
t=Xr⋅rs=(gx)r⋅(gi⋅gxj)s=gxr+si−rj−1xj=gsi=gM (mod p)t = X^r \cdot r^s = (g^x)^r \cdot (g^i \cdot g^{xj})^s \\= g^{xr + si - rj^{-1}xj} = g^{si} = g^M \ (\text{mod} \ p)
따라서 σ=(M,(r,s))\sigma = (M, (r, s))가 유효하다.
🚀

DSA 서명 (DSA Signature) 🔗

✅

키 생성 (DSA) 🔗

  1. 순환 부분군 G\mathbb{G} 생성
    • 소수 pp 선택
    • Zp∗\mathbb{Z}_p^*는 소수 pp에 대한 유한체의 곱셈 군
    • Zp∗\mathbb{Z}_p^*의 순서란 이 군에 속하는 모든 원소의 개수: p−1p-1
    • qq는 p−1p-1의 소인수 중 하나인 소수
    • 원소 개수가 qq인 부분군 G\mathbb{G}를 생성
  2. 부분군 G\mathbb{G}의 임의의 생성자 gg 선택
  3. Zq\mathbb{Z}_q에서 임의의 xx 선택 후 X=gx(modp)X = g^x \pmod{p} 계산
  4. 공개 키 pk=(p,q,g,X)pk = (p, q, g, X), 개인 키 sk=xsk = x를 반환
✅

서명 (DSA Signature) 🔗

비밀 키 sk=xsk = x와 메시지 MM이 주어졌을 때
  1. Zq∗\mathbb{Z}_q^*에서 임의의 kk 선택
  2. r=(gk(modp))(modq)r = (g^k \pmod{p}) \pmod{q} 계산
  3. s=k−1(H(M)+xr)(modq)s = k^{-1}(H(M) + xr) \pmod{q} 계산
  4. 서명 σ=(M,(r,s))\sigma = (M,(r, s))를 반환
✅

검증 (DSA Signature Verification) 🔗

공개 키 pk=(p,q,g,X)pk = (p, q, g, X)와 메시지 MM에 대한 서명 σ=(M,(r,s))\sigma = (M, (r, s))가 주어졌을 때
  1. 0<r<q,0<s<q0 < r < q, 0 < s < q를 확인
  2. w=s−1(modq)w = s^{-1} \pmod{q}를 계산
  3. u1=H(M)⋅w(modq)u_1 = H(M) \cdot w \pmod{q}, u2=rw(modq)u_2 = rw \pmod{q}를 계산
  4. v=(gu1Xu2(modp))(modq)v = (g^{u_1}X^{u_2} \pmod{p}) \pmod{q}를 계산
  5. v=?rv \stackrel{?}{=} r를 확인한다. 이 조건이 성립하면 1을 반환하고, 그렇지 않으면 0을 반환한다.
✅

정확성 (DSA Signature correctness) 🔗

v=gu1Xu2=gu1+xu2v = g^{u_1}X^{u_2} = g^{u_1+xu_2}
=gw(H(M)+xr)= g^{w(H(M)+xr)}
=gk(H(M)+xr)−1(H(M)+xr)= g^{k(H(M)+xr)^{-1}(H(M)+xr)}
=gk (mod p)→(∵s=k−1(H(M)+xr))= g^{k} \ (\text{mod} \ p) \rightarrow (\because s = k^{-1}(H(M)+xr))
⟹r(modq)=gk(modq)=gu1Xu2(modq)=v\Longrightarrow r \pmod{q} = g^k \pmod{q} = g^{u_1}X^{u_2} \pmod{q} = v