MOD calculation / reversing

[radugafener]

Hi all,

c = a^3 MOD b

"c" (297 digits) and "b" (308 digits) are known, they are not prime. Do I have chance to find "a" ?

(b-1)/3 does not have a cube root.
(b-1) MOD 3 = 0
b MOD 9 = 4
I have a valid pair ("a" and "c"). But, "c" is variable, so as "a".
"c" has to have 247 digits in hexadecimal format and last ~190 digits must or / and can be zero 0.

If there is a solution in case I replace "b" with other number which I decide, what shall I do to calculate "a" ?

Regards,

[xilman]

Originally Posted by radugafener

Hi all,

c = a^3 MOD b

"c" (297 digits) and "b" (308 digits) are known, they are not prime. Do I have chance to find "a" ?

(b-1)/3 does not have a cube root.
(b-1) MOD 3 = 0
b MOD 9 = 4
I have a valid pair ("a" and "c"). But, "c" is variable, so as "a".
"c" has to have 247 digits in hexadecimal format and last ~190 digits must or / and can be zero 0.

If there is a solution in case I replace "b" with other number which I decide, what shall I do to calculate "a" ?

Regards,

Ok, so you are trying to break a kilobit RSA implementation in which the public exponent is 3.

Good luck.

[retina]

Originally Posted by radugafener

Hi all,

c = a^3 MOD b

"c" (297 digits) and "b" (308 digits) are known, they are not prime. Do I have chance to find "a" ?

(b-1)/3 does not have a cube root.
(b-1) MOD 3 = 0
b MOD 9 = 4
I have a valid pair ("a" and "c"). But, "c" is variable, so as "a".
"c" has to have 247 digits in hexadecimal format and last ~190 digits must or / and can be zero 0.

If there is a solution in case I replace "b" with other number which I decide, what shall I do to calculate "a" ?

Regards,

Indeed, you can know all of a, b and c and yet still not be able to figure out the private key that matches 3. As xilman points out this is classic RSA. To find your answer it is sufficient to factorise b. If the b you have was chosen carefully as b=pq and both p and q are near, but not too near, each other in size then your chances of ever factorising using currently known mathematical methods are very slim. You might have a better chance by using a $5 wrench.

[radugafener]

:-) xilman, I am not intending to break kilobit RSA.
As I wrote that I have chance to replace "b" & "public exponent" with any number. But, I have to calculate "a" exactly because of "c" which has to have 247 digits (last ~190 digits should be zero, this is very important).
How can I choose / create my own RSA key (308 digits) with all modulus ?

[retina]

Originally Posted by radugafener

I am not intending to break kilobit RSA.

Okay, if you say so.

Originally Posted by radugafener

As I wrote that I have chance to replace "b" & "public exponent" with any number. But, I have to calculate "a" exactly because of "c" which has to have 247 digits (last ~190 digits should be zero, this is very important).
How can I choose / create my own RSA key (308 digits) with all modulus ?

Choose b=anything, e=1, d (private key)=1 and you're done.

If you can choose your own b then you can also compute d so reversing a from c is trivial.

[radugafener]

:) thanks
I just changed "public exponent" to 1. It is enough for me. "c" and "a" became same, and I didn't touch to "b". Because now "a" is smaller than "b" and "a" MOD "b" is always "a" = "c"
regards,