Re: Surrogate factoring, reasons for my concerns
From: James Harris (jstevh_at_msn.com)
Date: 07/14/04
- Next message: JD Geier: "Cryptography Materials"
- Previous message: David Wagner: "Re: Problems With Public Key Cryptosystems"
- In reply to: Jeroen Boschma: "Re: Surrogate factoring, reasons for my concerns"
- Next in thread: David C. Ullrich: "Re: Surrogate factoring, reasons for my concerns"
- Reply: David C. Ullrich: "Re: Surrogate factoring, reasons for my concerns"
- Reply: Jeroen Boschma: "Re: Surrogate factoring, reasons for my concerns"
- Messages sorted by: [ date ] [ thread ] [ subject ] [ author ] [ attachment ]
Date: 14 Jul 2004 13:02:34 -0700
Jeroen Boschma <boschma@fel.tno.nl> wrote in message news:<40F4DA2A.EA032B9E@fel.tno.nl>...
> James Harris wrote:
> >
> > Jeroen Boschma <boschma@fel.tno.nl> wrote in message news:<40F39740.590EB00B@fel.tno.nl>...
<deleted>
Um, well I finally took a look at your code.
You have multiple problems including some weird stuff.
Sigh.
> > > Conclusion: the algorithm is worthless in its present form.
> >
> > That's not surprising, but your conclusion is weird.
> >
> > 3% is actually rather good, and definitely good enough to cause
> > worries if your results hold with large numbers, though I doubt they
> > will.
> >
>
> It's easy for RSA to pick numbers which can not be factored by your algorithm (is necessary at all,
> see results below). So there's no security risk I guess. There's only a security risk if RSA runs
> out of options due to the performance of some algorithm.
Your data is useless as your code is screwy. GIGO.
>
> Matlab code is below, as quick and diry as it gets (tabs are not all OK due to copy/paste).
>
<deleted>
>
> % Get j.
>
> j = (f1+f2)/2;
Here's the first problem I noticed, and while I gave that example it
doesn't always work.
What you need to do is take (T^2 - 1)/4, assuming T is odd, factor it,
and then
j = f_1 + f_2
while what you have won't work if your f1 is even while your f2 is
odd.
If you were checking ALL combinations then that possibility will
necessarily present itself, and your code will flat out just screw it
up.
And there are two more mistakes I noticed before I quit bothering, and
one that I just find freaking annoying, as your first mistake--given
what I put in my post--is kind of understandable.
>
> % Get k.
>
> [k_num, k_denom] = get_k(j, N);
> gcd_input = j*k_num - N*k_num + N*k_denom;
Huh?
Your last mistake is in your calculation of k.
%*************************************************************************************************
> % Calculate k
> %*************************************************************************************************
>
> function [k_num, k_denom] = get_k(j, N)
>
> k_num = (-j*N + N^2*sqrt(j^2 - N^2 + 1));
> k_denom = (j^2 - N^2);
>
You forgot that it's "+/-" not just "+".
You need to check both possibilities wherever there's a square root
taken.
In a way it's a minor mistake, but I just kind of find it freaking
annoying.
Ok, so this guy's data is flawed.
Now I *assume* that this approach will not usually work, but at this
point, the jury is still out.
James Harris
- Next message: JD Geier: "Cryptography Materials"
- Previous message: David Wagner: "Re: Problems With Public Key Cryptosystems"
- In reply to: Jeroen Boschma: "Re: Surrogate factoring, reasons for my concerns"
- Next in thread: David C. Ullrich: "Re: Surrogate factoring, reasons for my concerns"
- Reply: David C. Ullrich: "Re: Surrogate factoring, reasons for my concerns"
- Reply: Jeroen Boschma: "Re: Surrogate factoring, reasons for my concerns"
- Messages sorted by: [ date ] [ thread ] [ subject ] [ author ] [ attachment ]
Relevant Pages
|
