RSA的签名方案流程如下：
-
1）生成公私密钥对
①选取两个大素数 p p p、 p p p，计算 n = p q n=pq n=pq及 n n n的欧拉函数 φ ( n ) = ( p − 1 ) ( q − 1 ) \varphi(n) = (p-1)(q-1) φ(n)=(p−1)(q−1);
②随机选取整数 e ( 1 < e < φ ( n ) ) e(1<e<\varphi(n)) e(1<e<φ(n))作为公钥，满足 gcd ( e , φ ( n ) ) = 1 \gcd(e,\varphi(n))=1 gcd(e,φ(n))=1，即 e e e 与 φ ( n ) \varphi(n) φ(n)互素;
③使用Euclid扩展算法计算私钥： d ≡ e − 1 m o d φ ( n ) d \equiv e^{-1} \mod \varphi(n) d≡e−1modφ(n)，即 e e e 的逆元(先选择 e e e再确定 d d d的原因是：加密的重要性大于解密的重要性)。 -
2）签名过程
设待签名的消息为 m m m，签名者利用安全的 H a s h Hash Hash函数产生消息摘要 h = H a s h ( m ) h=Hash(m) h=Hash(m)，然后计算签名： s ≡ h d m o d n s \equiv h^d\mod n s≡hdmodn。 -
3）验证过程
签名接收者收到消息 m m m和签名 s s s，计算消息摘要 h = H a s h ( m ) h=Hash(m) h=Hash(m)，然后，检验等式 h m o d n ≡ s e m o d n h \mod n \equiv s^e \mod n hmodn≡semodn。若成立，则签名有效；否则签名无效。
签名时使用
H
a
s
h
Hash
Hash函数可以防止利用同态的伪造攻击，有很好的抗攻击性。
RSA签名方案存在签名可重用的问题，同一消息在不同时刻签名不应是相同的。
RSA签名方案还存在签名可重用的问题，同一消息在不同时刻签名不应是相同的。这个问题可以通过在签名中引人随机数来解决。