高速可配置RSA密码协处理器的ASIC设计

公钥密码系统，也称为非对称密码系统，是密码学的一种形式。它有一对密钥：公钥和私钥。它们在数学上有一定的关系，但是很难从公钥得到私钥。公钥密码学的两个主要分支：

公钥加密：任何人都可以将消息（明文）加密成密文，但只有接收者才能生成有意义的密文。这样确保了数据的安全性，用于可靠性方面。

数字签名：发送者通过私钥加密的消息(明文)，可以被任何人通过公钥解密。因此证明了这条消息是发送者签名并且没被人修改过。这种方法用于数字签名与认证方面。

公钥制密码学中，目前应用最为广泛的是RSA公钥制密码算法[1]。RSA算法通过模幂运算实现，模幂运算是整个RSA算法的核心。在操作数较小的情况下，模幂运算比较简单，可以直接计算。但是为了保证必要的安全等级，一般采用512 bit或1 024 bit的密钥长度，在银行等需要更高安全等级的系统中，会采用更长位宽的密钥，模幂的难度随之成指数级增长。RSA算法安全性的保证和需要就像一把双刃剑，在给攻击者带来计算难度的同时也提高了运算的复杂度。

本文提出一种基于ASIC设计的高速、可配置的RSA密码协处理器体系结构，可实现256 bit到2 048 bit的RSA加密运算。该方案综合考虑RSA模幂和模乘算法的特点和瓶颈，采用改进的高基模乘算法和流水线结构，提高运算速度；采用DMA直接访问方式，消除协处理器与内存之间的通信速度瓶颈；数据输入输出都使用双口存储体，形成加解密数据流。

1 公钥密码算法RSA

1.1 RSA算法

RSA加密算法是目前在理论和实际应用中较为成功的公钥密码体制，它的安全性是基于数论中大整数分解为素数因子的困难性，这一困难在目前仍是一个NP问题。要建立一个RSA密码系统，首先任选两个大素数p、q，使：

N=p×q

并得到Euler函数:

Ψ(n)=(p-1)×(q-1)

然后任选一个与Ψ(n)互素的整数e作为密钥，再根据e求出解密密钥d，d满足：

d×e=1modΨ(n)

事实上，加密密钥e和解密密钥d是完全可互换的，因此在求e或d时，不论先假设哪一个，再由它去求另一个都是一样的。对某个明文分组M和密文分组C，加密和解密的过程如下：

加密过程：

C=MemodN

而解密过程是：

M=CdmodN

RSA加解密就是做模幂运算的过程，而模幂运算是通过一系列的模乘运算得到的。模幂算法根据幂指数扫描顺序不同可以分为两种：从左往右的L-R算法和从右往左的R-L算法。

算法一：R-L模幂算法

式中n为指数e的位数，P为中间变量

输入：M，e，N；

输出：C=Me modN；

(1)P=M；C=1；

(2)for i=0 to n-2；

(3)if e[i]=1 then C=C×P mod N；

(4)P=P×P mod N；

(5)next i；

(6)if e[n-1]=1 then C=C×P mod N；

(7)return C；

算法二：L-R模幂算法

输入：M，e，N；

输出：C=Me modN；

(1)if e[n-1]=1 then C=M，else C=1；

(2)for i=n-2 to 1；

(3)C=C×C mod N；

(4)if e[i]=1 then C=C×M mod N；

(5)next i；

(6)return C；

从以上两种算法可以看出，一次模幂运算需要进行N次平方模运算和平均N/2次乘法模运算；但在从右往左的扫描中，乘法和平方是相互独立的，可以并行。因此可以增加一个N位的乘法器，一个做乘法，一个做平方，这可以显著提高一次模幂运算的速度。本文面向高速应用场合，因此采用R-L模幂算法。

在RSA算法中，不论是加密过程还是解密过程，都有一个共同的模乘运算(ABmod N)，这个看似简单的运算，需要做一次乘法和一次除法，最后取余数。但由于M，e，C，d，N等参数的长度通常是1 024个二进制位或更高，使得模幂运算量巨大，很难在一般的协处理器上或处理器上运行，直到1985年由Montgomery提出了一种免除法的模乘算法[2]，才使RSA算法在硬件和软件中得以实现。

1.2 Montgomery模乘算法

Montgomery算法的基本思想是把一个大整数转换为一个模R(R通常取2r)的余数表示形式，用转换后的余数进行一系列模乘运算，最后再转换为正常的表达形式。将计算A*B mod N时的mod N的除法运算转化为简单的移位运算，能够有效地提高模乘运算的速度。

算法三：Montgomery算法

设N为模数，R是2的整数幂，且R>N，并令R-1和N′满足0-1-1-NN′=1成立。

输入：A，B，R，N；

输出：c=M(A，B)=A*B*R-1 modN

(1)T=A*B；

(2)m=(Tmod R)*N′ mod R；

(3)c=(T+mN)/R；

(4)if c>=N return c-N；

(5)else return m；

该算法不能直接实现RSA算法，需要进行相应的预处理才能消除R-1带来的影响（见算法五）。该算法仍然包含大整数的乘法，因此需要对其进行改进，使用高基模乘算法（见算法四），细化为小整数的乘法，以便于硬件实现。另外，该算法最