On the 2nd page of "New probabilistic public-key encryption based on the RSA cryptosystem" by Roman'kov (PDF), at last it says Alice can find "f" of order "l" with least probability of (1-1/l). I cannot understand how they came up with this probability. Can anyone help me with this.
$\begingroup$
$\endgroup$
9
-
$\begingroup$ If everything else failed, contacting the author turned out to usually work quite well... $\endgroup$– SEJPMMay 13, 2016 at 19:14
-
$\begingroup$ I have mailed him. But, I dont think this would work.. $\endgroup$– MayankMay 13, 2016 at 19:26
-
3$\begingroup$ This looks very fishy. Having skimmed through the abstract and introduction, the number of incorrect statements made me stop reading. $\endgroup$– AlephMay 13, 2016 at 19:59
-
$\begingroup$ I was trying to implement the paper, but with all these problems it is impossible to implement. $\endgroup$– MayankMay 14, 2016 at 6:38
-
2$\begingroup$ I would not take this seriously. It's presentation is certainly sub-standard. It has no proof of its arguments and is very suspect. $\endgroup$– Yehuda LindellMay 14, 2016 at 19:14
|
Show 4 more comments
1 Answer
$\begingroup$
$\endgroup$
3
The paper is rather sloppily written, however it can be changed into the correct statement.
The statement in the paper is:
She takes randomly elements $f \in F^*_p$ and checks whether or not $f^{2x}=1$. With probability at least $1 − 1/\ell$ she finds $f$ of order $\ell$.
As written, that's wrong. However, if we modify it to:
She takes a random element $f \in F^*_p$ and computes $g = f^{2x}$; if $g \ne 1$ (which will happen with probability $1 − 1/\ell$), then $g$ will be of order $\ell$.
Then it is a correct statement (and is the standard way of generating random elements of order $\ell$).
There are a number of places in the paper like this; places where, as written, it doesn't make much sense, but if you know your number theory, you can deduce what the author actually meant. I suspect that this can be modified to make a secure cryptosystem; however whether it does have any advantage over RSA (and whether it's actually safe for multiple users to use the same modulus and different exponents) is far less clear.
-
$\begingroup$ Thanks a lot. I have now understood what was meant from that line.. $\endgroup$– MayankMay 16, 2016 at 0:16
-
$\begingroup$ An OT but related question: The author of the paper doesn't give detailed specifications of how the subgroups M and H are to be chosen, if I don't err. Couldn't the issue of appropriate vs. inappropriate choice of the subgroups eventually have some significance in the resulting security obtained? $\endgroup$ May 18, 2016 at 10:13
-
$\begingroup$ @Mok-KongShen: you are correct; since those subgroups are exposed, a bad choice could make $pq$ easy to factor. If I were implementing this, I would make $p-1 = 2ab$ and $q-1 = 2cd$ ($a, b, c, d$ prime), and make subgroup $M$ the one of size $ac$ and $H$ the one of size $bd$. However, the paper doesn't say that... $\endgroup$– ponchoMay 18, 2016 at 12:21