need help for doing modular exponentiation in RSA algorithm

[srilekha]

HI everybody,

I need some help regarding Implementing modular exponentiatin in hardware (FPGA). I am making use of Montgomery multiplication to achieve modular exponentiation by repeated squaring and multiplication.

it involves for loop whose iteration is of no of bits of the key.

for ex if the key is of 512 bit size the loop has to be executed 512 times.or it will take 512 clk cycles.
my aim is to encrypt the data with the key of size 2048 bits.


is there any way to do this.

thanks and regards,
Srilekha

 

[AONA]

there are many version of montgomery algorithm.if you want do it with 2048 operands and high speed , high radix is a better choice, eg. FIOS, Booth recode.

Added after 12 minutes:

Can we talk about it by Email.
My email is yuanyang.zhang@gmail.com
Please contact me!

 

[srilekha]

Re: need help for doing modular exponentiation in RSA algori

hi ,

Thanks a lot for giving me idea regarding this.right now i am proceeding with radix 2.
i am not able to do understand other radix especially the booth algorithm.

can u give me some details regarding that,

function ModExp(M; e; n) f n is an odd number g
Step 1. Compute n0 using the extended Euclidean algorithm.
Step 2. M = M * r modN
step 3 x' = r mod N

where r is 2 ^ k modn - k is no of bits of m ,e,n

step 4 for i -= k-1 to 0
{
step 5 x' = montpro (x' , x');
step 6 if (e = 1)
begin
x` = montpro(m',x');
end
}
step 7 x= montpro (x',1);
return x

i am getting the exact result. the montgomery i am using is faster montgomery.
i have a doubt regarding that
when i find the mont pro of montpro (3 (a),3 (b) , 13(N))
i am getting the result as 3

and i am getting the required result of modulus exp when i use faster montgomery.
but its given it will yield (ab * 2^-n) mod N;
in this case a = 3 b = 3 and n = 4 bits
N = 13

so the expected result is 3 * 3 * 2 ^ -4 mod 13 = 0; i am too much confused .right now i have just implemented whats given in the algorithm and getting the result but wondering how it works.pls help me to understand it.

Thanks and Regards ,
Srilekha

 

[AONA]

you have make a wrong compute.3 * 3 * 2 ^ -4 mod 13 is not equate to 0,but just 3.
2 ^ -4 mod 13=9,so 3 * 3 * 2 ^ -4 mod 13=3 * 3 * 9 mod 13=3.

 

[aslijia]

there is an other algorithm, proposed by C.C Yang, can be used on implement based on systolic array structure. Have you thought about it?

Added after 4 minutes:

ps: i am working on modular multiplication now, and I will be very glad if I have honor to join you.

 

[AONA]

To aslijia,
what do you think about CSA structure?Compared to systolic array, which one is better?i have implement modular multiplication with CSA architecture, and know less about systolic array.
Now i am working on scalable Montgomery modular multiplication, which is proposed by KOC.

 

[aslijia]

TO aona
i am working on systolic array structure, and i think it is better than CSA. But i haven't compared them in detail yet. i will do it if possible.

structures based on systolic or CSA are different because they are using differern algorithm. And Yang-montogmery algorithm can be implemented by using serial-parallel multiplication, so it must be very small in silicon area. i.e.,in Yang-montgomery algorithm, we don't have the operate: sum=sum+A*b+....,
but sum=sum+x+qM. here x=A*B was pro-calculated.

 

[AONA]

pro-calculation in Yang-montgomery algorithm is x=A*B.this is a big integer multiplication. If these is a multiplier to be utilized, it is a better choice.
Are you chinese?
my qq is 77566382.add me.

 

[aslijia]

so, we can use an serial-parallel multiplier.
i have add you. i am in shannxi

 

[srilekha]

HI Aono how 2^-4 mod 13 is 9 pls give me clarifications

i am just amazing how it works pleas give some brief explanation regarding this.

i am just keep on looking into it for a quiet long time.

 

[aslijia]

Re: need help for doing modular exponentiation in RSA algori

now let 2^-4 mod 13 ≡ x mod 13
1 mod 13 ≡ x *16 mod 13
then one of the solution is x=9.

am i make it clarifying?

 

[srilekha]

Re: need help for doing modular exponentiation in RSA algori

hi friends,

u have really helped me a lot in understading the modulus inverse.special thanks to Aona.
right now i am using L-R algorithm for RSA which consumes ((n + (no of bits set in exponent e) * n )clks.msb bit of the exponent is checked first .
but i have seen in R - L the squaring and multiplication can be done in parallel.where lsb of exponent is checked first. i am not able to get the result if i do the squaring and multiplication in parallel.


can anyone help me .

Thanks and regards,

Srilekha

 

[aslijia]

what do you mean by saying"i am not able to get the result if i do the squaring and multiplication in parallel."?

do you try to use the L-R circuit(if you are doing a circuit) to perform a R-L algorithm or something others?

 

[srilekha]

Re: need help for doing modular exponentiation in RSA algori

Hi aslija,

I was checking both R_L and L_R with a sample value
2^10 mod 13 .i have done some mistakes in calculation and was thinking i dint get the exact value of 2^10 mod 13 while using R_L method.but i have found the mistake and now i am proceeding with R_L .Thanks for giving me idea in modulus inverse

Thanks and Regards,
Srilekha

 

[gold_kiss]

Re: need help for doing modular exponentiation in RSA algori

Anyone can give me links to good papers on RSA hardware implementation.

 

[research235]

Hello Gold Kiss

Please look for papers in IEEE, if u have access, else there is one book abt Cryptography, It has delated explanation of every thing ..

suresh