Hello,

I tried to write a code for CRT-RSA. The encryption is kinda easy and like the normal RSA:

Public key given: (e,N)=(5,851); private key: (d,dcp,dcq,p,q)=(317,29,9,37,23)

with the result:

                      [116, 101, 115, 116]
                       [676, 645, 144, 3]
                      [100, 70, 715, 243]

So, know i tried the following:

that also works pretty fine; dcp and dcq are the CRT-RSA-exponents, and gives:

                        [10, 16, 33, 3]
                          [9, 1, 6, 3]

So now my try for the next step:

but it doesnt work...

the results are:

Why does Maple take the whole vector for y? I dont get it....

Note: if d<sqrt(N), then d=dcq=dcp and the Decryption of normal RSA can be used:

therefore the line:

works as decipher1 already.

So thanks for any help!

Hello again,

for a paper I need to cipher and decipher with the standard RSA-procedure.
My problem is, that my numbers are really large.

As normally it's just, given a public key (e,N) and a private key (d,p,q), p,q are primes, and the plaintext:

encrypt: b^e mod N = c

decrypt: c^d mod N = b

That works cause ed = 1 mod (p-1)(q-1) (Euler's Phi-Function) and gcd(e,N)=1

With little numbers thats no problem. But increasing e and N, i thought using the powmod function will help:

b&^e mod N = c but

c&^d mod N <> b.

So it doesnt work anymore and I really dont get why...

thanks for help, I'm really lost here..

Hello,

I have a question. I have to compare the times and steps taken by an algorithmus (which contents a loop).

So for time there is the time()-function, right? And is there any similar function for the steps taken?

So far i use a variable increasing by 1 each time, but i think there is an more elegant way to do it, which I just don't know.. :D

Thanks for any help!

Heyho,

I'm pretty new to Maple (started Monday). And I don't know how to solve (or even why it exists) the following error:

S3() generates two integers, one converted from a random 568-Bit-number "e" and one converted from a random 160-bit number "kp1", satisfying gcd(e,kp1)=1.
That works pretty fine so far.

Now I need two specific numbers, x and y defined by:

And I use the proc S4 to get them:

Sometimes, the error occurs "Error, (in S4) the modular inverse does not exist", and I dont get why,... I tried to fix it, with the "while"-loop, but it didnt work out yet.

Someone knows how to solve this problem?
Thanks!

Hello,

I'm a bit lost, cause I Have to programm the "Schema A" from Wu/Sun with Maple. It's about Rebalanced-CRT-RSA, and therefore a key generation algorithm.

Unfortunately I havn't worked with Maple (or similar programms) yet. So if somebody will help me, that would be really kind :)

Here's the Algorithm (Source: Wu/Sun, Design of Rebalanced RSA-CRT for fast Encryption):

Step 1. Randomly select an odd number e of 568 bits.

Step 2. Randomly select a number kp1 of 160 bits, such that gcd(kp1, e) = 1.

Step 3. Based on Theorem 4.1, we can uniquely determine two numbers dp, k_{p1} < dp < 2k_{p1},
and P , e < P < 2e, satisfying ed_p = k_{p1}P + 1.
Step 4. Factor P as P = k_{p2} · p_0 such that k_{p2} is a number of 56 bits and p (= p_0 +1) is a prime
number. If this is infeasible, then go to Step 2.
Step 5. Randomly select a number k_{q1} of 160 bits, such that gcd(k_{q1}, e) = 1.
Step 6. Based on Theorem 4.1, we can uniquely determine two numbers dq, k_{q1} < d_q < 2k_{q1},
and Q, e < Q < 2e, satisfying ed_q = k_{q1}Q + 1.
Step 7. Factor Q as Q = k_{q2} · q_0 such that k_{q2} is a number of 56 bits and q (= q_0 +1) is a prime
number. If this is infeasible, then go to Step 5.
Step 8. The public key is (N, e); the secret key is (d_p, d_q, p, q).

Thank you for any help!

Edit2: I'm a fool, the integers arent of the right form, so they're not 568-bit/160-bitform :/

Edit:

I continued tryin, and I think i got at least Step 1-3:

Step 1+2: 

restart; 
with(RandomTools); 
BeidesGCD := proc () 
local a, b, A, B, C; 
global e, kp1; B := proc () 
b := Generate(nonnegint(range = 2^568)) 
end proc; 
while length(b) <> 171 do B() end do; 
while type(b, odd) = false do B() end do; 
A := proc () 
a := Generate(nonnegint(range = 2^160)) 
end proc; 
while length(a) <> 49 do A() end do; 
while gcd(a, b) <> 1 do A() end do; 
e := b; print(b); 
kp1 := a; 
print(a); 
gcd(e, kp1) 
end proc 

and the numbers needed for Step 3:

x := 1/e mod kp1; 
y := (e*x-1)/kp1; 

dp := x+kp1; 
P := y+e; 

But the next step causes problems, is it even possible to tell Maple "sth is infeasible"?