###### tags: `pqc` `tutorial` `ntru`
[索引](/oiLTvejNR0Cy4Ct-ydK-QQ)

# 實際操作範例
這裡我們會使用[SageMath](/16H1Q1EhSemws4CDZCxmig)來進行實作。

## 參數
此次要傳遞的訊息$m$為$x^3 + x$。
* $N=5$
* $p=3$, $q=29$, $d=1$
* $f=x^4+x^3-1\in L(2,1)$
* $g=x^3-x^2\in L(1,1)$

## 實作
### 找出$f$在$R_p,R_q$內的乘法反元素:

sage: p=3; q=29      # 設定參數
sage: mod=x^5 - 1
sage: R=PolynomialRing(ZZ, x).quotient_ring(mod)   # 設定運算的環
sage: Rp=PolynomialRing(Integers(p), x).quotient_ring(mod) # 設定m所在的空間
sage: Rq=PolynomialRing(Integers(q), x).quotient_ring(mod) # 設定c所在的空間
sage: f = x^4 + x^3 - 1; g = x^3 - x^2 # 設定f, g
sage: fp = 1/Rp(f); fq = 1/Rq(f)  # 到這裡就算出fp跟fq了
sage: fp; fq # print出fp, fq

結果如下：

因此我們就知道:
* $f_p = 2x^3 + 2x^2 + x + 2$
* $f_q = 24x^4 + 8x^3 + 3x^2 + 11x + 13$

### 算出公鑰$h$並隨便找個$r\in L(d,d)$來跟$h$加密$m$:

sage: h = fq * Rq(g) # 生成公鑰
sage: m = x^3 + x; r = x^4 - x # 設定m跟一個隨便取的r
sage: c = Rq(p) * Rq(h) * Rq(r) + Rq(m) # 在Rq下算出c
sage: c # print出c

結果如下:
Note: 這裡的$m(1)=c(1)\ (mod\ 29)$，是可以從$c$得到$m$在$x=1$的資訊的。

因此我們就得到密文$c$了。注意這裡加密的動作並不須要$(N,p,q,h)$以外的資訊。

### 用私綸$f$來解密$c$:
#### 算出$Rq$下的$a$

sage: a = Rq(f) * c # 在Rq下算出a = f*c (c原本就在Rq內)
sage: a # print出a

結果如下：
所以我們移動係數後得到$a = -2x^4 + 2x^3 + 4x^2 -3x + 1$。
我們可以確認移動係數後的結果確實在$R$下成立(沒有溢出)：

sage: a = p * R(r) * R(g) + R(f) * R(m) # 參Original NTRU最後解密的推導
sage: a # print出a

結果如下：

#### 算出$m=a\cdot f_p$

sage: Rp(a)*Rp(fp) # 直接print出m的結果

結果如下：
我們就成功還原了$m = x^3 + x$。