用于蒙哥马利乘法的运算电路及密码电路

摘要

本发明提供一种用于蒙哥马利乘法的运算电路，其能够仅使用1端口RAM进行蒙哥马利乘法。该运算电路能够执行：从对a[s-1:0]和b[s-1:0]进行储存的同步式1端口RAM的存储器(M2)读出b[i]并储存到寄存器R1的第一读出处理；从存储器(M2)读出a[j]，从对t[s-1:0]进行储存的同步式1端口RAM的存储器(M1)读出t[j]，从寄存器(R1)读出b[i]，从寄存器(R2)读出值RC，输入进行计算t[j]+a[j]*b[j]+RC的积和运算处理的积和运算电路10的第二读出处理；将运算结果数据(FH)写入寄存器(R2)，并且将运算结果数据(FL)作为t[j]写入到存储器(M1)的写入处理，在第一读出处理执行后，执行第一子循环处理，该第一子循环处理反复执行第二读出处理、积和运算处理、写入处理。

主权项

一种用于蒙哥马利乘法的运算电路，其中，构成为具备：积和运算电路，进行积和运算处理，在该积和运算处理中，受理位宽度r的第一变量、第二变量、第三变量、第四变量，对所述第三变量、所述第一变量和所述第二变量的求积结果、以及所述第四变量的和进行运算，输出位宽度2r的运算结果数据；第一存储器，以具备对位宽度r、元素数s的中间结果储存用数组进行储存的存储区域的同步式1端口RAM构成，将所述中间结果储存用数组的各元素作为所述第三变量向所述积和运算电路输出；第二存储器，以具备对位宽度r、元素数s的第一数组和第二数组进行储存的存储区域的同步式1端口RAM构成，将所述第一数组的各元素作为所述第一变量向所述积和运算电路输出；被乘数储存用寄存器，从所述第二存储器以元素单位受理并存储所述第二数组，作为所述第二变量向所述积和运算电路输出；进位寄存器，受理并存储由所述运算结果数据内的高位r位构成的高位位侧数据，作为所述第四变量向所述积和运算电路输出，该用于蒙哥马利成分的运算电路构成为能够执行下述处理，即：第一读出处理，从所述第二存储器读出以规定的第一循环计数器值表示的所述第二数组的元素并储存到所述被乘数储存用寄存器；第二读出处理，从所述第二存储器读出以规定的第二循环计数器值表示的所述第一数组的元素，从所述第一存储器读出以所述第二循环计数器值表示的所述中间结果储存用数组的元素，读出所述被乘数储存用寄存器的值，读出所述进位寄存器的值，分别输入到所述积和运算电路；以及写入处理，将所述高位位侧数据写入所述进位寄存器，并且将由所述运算结果数据内的低位r位构成的低位位侧数据，作为以所述第二循环计数器值表示的所述中间结果储存用数组的元素，写入所述第一存储器，在所述第一读出处理执行后，执行第一子循环处理，在该第一子循环处理中，反复执行所述第二读出处理、所述积和运算处理、所述写入处理、以及所述第二循环计数器值的更新。