Fujitsu cracks 278-digit crypto

firejuggler · 2012-06-19, 09:05

http://www.theregister.co.uk/2012/06..._world_record/

Code:

We were able to overcome this problem by making good use of various new  technologies, that is, 
a technique optimising parameter setting that  uses computer algebra, a two dimensional search
 algorithm extended from  the linear search, and by using our efficient programing techniques to
 calculate a solution of an equation from a huge number of data, as well  as the parallel programming
 technology that maximises computer power.

and the original link
http://www.fujitsu.com/global/news/p...120618-01.html

Batalov · 2012-06-19, 09:45

"21 personal computers (252 cores) in 148.2 days?" (The 0.2 days precision looks quite out of place.) Sheesh...

firejuggler · 2012-06-19, 09:56

Now it's time to generalise 2048-bit crypto...

even if a wrench might work far faster...
http://xkcd.com/538/

poily · 2012-06-19, 09:57

It probably has nothing to do with factoring. More like with DL over some exotic group or EC.

fivemack · 2012-06-19, 12:01

http://www.nict.go.jp/en/press/2012/...20120618en.pdf is a PDF describing what they've done: there's an index-calculus-like attack which gets you from an EC problem over GF(3^97) to a discrete-log one over GF(3^582), and they've then done that one using the function field sieve.

Robert Holmes · 2012-06-19, 12:10

Quote:

Originally Posted by fivemack

http://www.nict.go.jp/en/press/2012/...20120618en.pdf is a PDF describing what they've done: there's an index-calculus-like attack which gets you from an EC problem over GF(3^97) to a discrete-log one over GF(3^582), and they've then done that one using the function field sieve.

What do you mean "index-calculus-like"? It's simple discrete log transfer by evaluating pairings.

Batalov · 2012-06-20, 06:31

So it has asymptotically equivalent difficulty to SNFS? (Not to GNFS?)
Why did they compare it to the 676-bit GNFS factorization?

(I am only echoing Tom. I am not that smart. Also.)

fivemack · 2012-06-20, 10:31

I think they're comparing it with the function-field-sieve in GF(3^426) (a 676-bit number) which an NICT group did and described in http://eprint.iacr.org/2010/090.pdf. The press release doesn't mention factorisation.

The uni-saarland link is for algorithms in large prime characteristic (though both general-prime and special-prime), which are rather different from the function field sieve that is used in small characteristic.

akruppa · 2012-06-20, 20:03

Moved from Factoring to Science since it's not a factorization problem they solved.

2012-06-19, 09:45	#2
Batalov "Serge" Mar 2008 Phi(4,2^7658614+1)/2 23·439 Posts	"21 personal computers (252 cores) in 148.2 days?" (The 0.2 days precision looks quite out of place.) Sheesh... Attached Thumbnails

2012-06-19, 09:56	#3
firejuggler "Vincent" Apr 2010 Over the rainbow 2884₁₀ Posts	Now it's time to generalise 2048-bit crypto... even if a wrench might work far faster... http://xkcd.com/538/ Last fiddled with by firejuggler on 2012-06-19 at 09:57

2012-06-20, 06:31	#7
Batalov "Serge" Mar 2008 Phi(4,2^7658614+1)/2 10097₁₀ Posts	So it has asymptotically equivalent difficulty to SNFS? (Not to GNFS?) Why did they compare it to the 676-bit GNFS factorization? (I am only echoing Tom. I am not that smart. Also.) Last fiddled with by Batalov on 2012-06-20 at 06:35

2012-06-20, 10:31	#8
fivemack (loop (#_fork)) Feb 2006 Cambridge, England 2×7×461 Posts	I think they're comparing it with the function-field-sieve in GF(3^426) (a 676-bit number) which an NICT group did and described in http://eprint.iacr.org/2010/090.pdf. The press release doesn't mention factorisation. The uni-saarland link is for algorithms in large prime characteristic (though both general-prime and special-prime), which are rather different from the function field sieve that is used in small characteristic. Last fiddled with by fivemack on 2012-06-20 at 10:36

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Crypto News	Nick	Tales From the Crypt(o)	52	2020-12-17 21:16
ElGamal crypto without prime	ElChapo	Math	9	2017-06-10 03:26
25-GPU cluster cracks every standard Windows password in <6 hours	swl551	GPU Computing	4	2012-12-22 01:32
Crypto 2007	R.D. Silverman	Lounge	2	2007-08-08 20:24
crypto game	MrHappy	Lounge	0	2005-01-19 16:27

2012-06-19, 09:57	#4
poily Nov 2010 2·5² Posts	It probably has nothing to do with factoring. More like with DL over some exotic group or EC.

2012-06-19, 12:01	#5
fivemack (loop (#_fork)) Feb 2006 Cambridge, England 2·7·461 Posts	http://www.nict.go.jp/en/press/2012/...20120618en.pdf is a PDF describing what they've done: there's an index-calculus-like attack which gets you from an EC problem over GF(3^97) to a discrete-log one over GF(3^582), and they've then done that one using the function field sieve.

2012-06-20, 20:03	#9
akruppa "Nancy" Aug 2002 Alexandria 4643₈ Posts	Moved from Factoring to Science since it's not a factorization problem they solved.