基于余数系统的RSA密码处理方法及协处理器

摘要

本发明涉及信息技术安全及微处理器设计。为能够加速RSA模乘运算速度，提高RSA加解密性能，本发明采取的技术方案是，基于余数系统的RSA密码处理方法，采用RSA算法进行加解密运算，采用L-R二进制扫描模幂算法进行RSA算法的大数模幂运算，所述改进的Montgomery算法具体为：将1024bit的大数表示成余数系统下的数，即两组33个32bit的小数，以及1个冗余基下表示的32bit的数，表示过程即求模过程，分解成的32bit小数分别独立参与32bit的模乘、模乘累加、模加运算，并且各个32bit数据之间不存在依赖，进行并行执行运算。本发明主要应用于信息技术安全及微处理器设计。

主权项

1.一种基于余数系统的RSA密码协处理器，其特征是，基于TTA架构来实现1024bit的RSA加解密算法，TTA架构是把运算的任务分配到各个功能单元，每个功能单元都由三类寄存器组成，即Operand寄存器、Trigger寄存器和Result寄存器，其中Operand寄存器作为运算操作数，Trigger寄存器也是运算的操作数，但给Trigger寄存器传输数据时，该功能单元的运算被触发，经过约定的时钟周期后，运算得到最终结果并存于Result寄存器；整体结构为：采用8条总线来进行数据之间的传输，需要进行数据通讯的功能单元之间通过总线进行连接，功能单元运算出来的结果放在功能单元的结果寄存器，通过总线传输到需要的功能单元，即需要进行数据通讯的功能单元之间通过总线进行相互连接；功能单元包括：处理器中包括2个存储器访问功能单元（LDST）、3个查表单元(LUT）、1个寄存器组RU、1个跳转功能单元JMP、1个算术逻辑运算单元ALU和8个模乘累加功能单元(MMAC)，前述处理器各组件都直接连接到总线上；存取数据单元是唯一能与数据存储器Data Memory进行交互的功能单元，存储器访问功能单元访问数据存储器Data Memory时，支持两种寻址方式：直接寻址和偏移寻址，完成直接寻址取数、直接寻址存数、偏移寻址取数和偏移寻址存数；查表单元是与ROM进行交互的功能单元；查表单元完成以4Bank形式的查表，即同一周期从ROM里Load4个在同一地址上的32bit预计算数据，以及以Burst形式加载32个连续地址存放的预计算数据；寄存器组用来暂存操作数或者运算结果，跳转功能单元用来支持绝对跳转、条件跳转和循环操作；除总线外，功能单元之间还设计了额外的数据通路：其中第二个存储器访问功能单元2和前四个模乘累加功能单元之间、第3个查表单元和后四个模乘累加功能单元之间存在着直接的数据通路；处理器中的模乘累加功能单元是进行模乘运算的核心计算功能单元，主要完成模乘、模加、模乘累加操作；算术逻辑运算单元用来实现包括模加、模减和32bit数左移一位的逻辑功能;模乘累加功能单元有两个Operand寄存器、一个Trigger寄存器和一个Result寄存器，两个Operand寄存器分别为乘数寄存器和模数寄存器，功能单元延时为3，支持三种触发方式mul、mac和clr，能够完成模乘、模乘累加和清零操作；本模乘累加功能单元分三级流水来完成模乘累加功能：第一级流水完成两个32bit的数相乘；第二级流水将第一级流水产生的64bit乘法结果进行模（2³²-c_i）的运算，得到(a*b)mod(2³²-c_i)的结果，其中a、b为任意32bit数据；第三级流水为完成累加功能，即将本次模乘结果与上一次模乘结果进行累加；其中在第一级流水中，硬件上由一个32bit×32bit的乘法器组成，并将两个32bit的乘数相乘结果存入第一级寄存器中，模数则直接寄存一级；其中在第二级流水中，假设P为第一级流水产生的64bit乘法结果，m_i为模数，即2³²-c_i，其中c_i为不大于2¹⁴-1的数，p₁表示P的高32bit，p₀表示P的低32bit，则：得到的p₁c_i+p₀中，p₁不大于32bit，c_i不大于14bit，p₀为32bit，所以p₁c_i+p₀不大于47bit；硬件上由一个14bit×32bit的乘法器和一个48bit的加法器组成，同理，令p′＝p₁c_i+p₀再执行一次这样的操作得到(p'₁c_i+p'₀)mod(2³²-c_i)，此时得到的p′₁不大于14bit，c_i也不大于14bit，p′₀不大于32bit，相加后的p′不大于33bit；硬件上由一个14bit×14bit的乘法器和一个33bit加法器组成比较p′＝p₁c_i+p₀与2³²-c_i的大小，如果大于2³²-c_i则进行一次相减操作，此时得到的结果便是(a*b)mod(2³²-c_i)；硬件上由一个33bit加法器和一个两路选择器组成；并将计算结果寄存到第二级寄存器中，模数则继续寄存一级；在第三级流水中，主要完成(a'+b')mod(2³²-c_i)，其中a'为模乘后得到的结果，b'为上次累加的结果；模乘累加功能单元的第三级流水中第一个加法器完成c'＝a'+b'，第二个加法器主要完成d＝c'+c_i，后面的两个多路选择器为，如果d大于2³²，则执行一次相减操作，若d小于2³²，则d即为所得结果；并将计算的最终结果存入第三级寄存器中;算术逻辑运算单元包括两个Operand寄存器、一个Trigger寄存器和一个Result寄存器，trigger type包括3个信号，算术逻辑运算单元在一个时钟周期内只有一个trigger type信号有效，触发后一个周期延时后得到结果，结果放在Result寄存器里面；在算术逻辑运算单元的内部结构中，有模加和模减两种运算，主要完成：(a+b)mod(2³²-c_i)或(a-b)mod(2³²-c_i)，其中alu1_o_mod为模数操作数寄存器，这里模数都是2³²-c_i的形式，送给alu1_o_mod的数是c_i,而不是2³²-c_i，算术逻辑运算单元在各数据到达后先根据alu_type来选择是完成哪种操作，如果是alu_type是001，则完成模加运算，010完成模减运算，100完成对alu_t_dat的左移位操作；算术逻辑运算单元首先对alu1_o_subtractor进行按位取反并在最低位后补1操作，和直接在最低位的后一位补0操作，对alu_t_dat进行最低位的后一位补1操作，这样硬件实现上就可以利用一个多路选择器进行选择原来的数据还是数据的补码，用一个33bit的加法器完成加法或减法的操作；同理，在得到加或减的结果后，做模时采用同样的方法，只需一个多路选择器和一个加法器即可完成；最终由trigger type信号来路选最终的计算结果，并写到结果寄存器中。