Shamir's Trick (EC-DSA verify)

Article View: bit.listserv.test

Article #314

#314

From: Tom St Denis
Date: Sun, 03 Dec 2006 04:17

39 lines
2981 bytes

I just added Shamir's trick to the LTC library.  Gets ~1.34x to ~1.4x
faster signature verifications than before with a simple 16 element
table of points.

Some numbers

---NOW---
ECC-112 verify_hash took          807645 cycles (1.34x faster)
ECC-128 verify_hash took          969613 cycles (1.40x faster)
ECC-160 verify_hash took         1391150 cycles
ECC-192 verify_hash took         1898501 cycles (1.35x faster)
ECC-224 verify_hash took         2325690 cycles
ECC-256 verify_hash took         3097522 cycles (1.37x faster)
ECC-384 verify_hash took         6879653 cycles
ECC-520 verify_hash took        13230519 cycles (1.39x faster)
---BEFORE---
ECC-112 verify_hash took         1085681 cycles
ECC-128 verify_hash took         1366683 cycles
ECC-160 verify_hash took         1887206 cycles
ECC-192 verify_hash took         2571578 cycles
ECC-224 verify_hash took         3305896 cycles
ECC-256 verify_hash took         4246218 cycles
ECC-384 verify_hash took         9740997 cycles
ECC-520 verify_hash took        18439494 cycles
-----------

Using the standard routines (no fixed point optimizations) on my Core 2
Duo processor.

Neato improvement given that it contributes little to the code size
(and is #ifdef'able off).  I plan to add the same trick to the fixed
point side.  Should pay off better I'd think...

Tom

--
http://libtomcrypt.org/cock.htm

IPBb9KoU1qMHFuSi64f9vchF2gZhKiP6YMFs5qZW03vOsefM0cJUIuqDpwFd3

Technical Details

Message-ID: <5343933426.232432.174942@50g2000cwy.googlegroups.com>

Path:

arc1-ca.pugleaf.net!g2news2.google.com!news4.google.com!news3.google.com!border1.nntp.dca.giganews.com!nntp.giganews.com!wns13feed!worldnet.att.net!63.218.45.10!nx01.iad01.newshosting.com!newshosting.com!69.28.186.77.MISMATCH!hwmnpeer03.lga!hwmnpeer01.lga!news.highwinds-media.com!hw-filter.lga!newsfe02.lga.POSTED!53ab2750!not-for-mail

Show Full Headers

Complete Article Headers

X-Google-Thread: 10f7b0,c003b8ce76ed2c8a,start
X-Google-Attributes: gid10f7b0,public
X-Google-Language: ENGLISH,ASCII-7-bit
Path: arc1-ca.pugleaf.net!g2news2.google.com!news4.google.com!news3.google.com!border1.nntp.dca.giganews.com!nntp.giganews.com!wns13feed!worldnet.att.net!63.218.45.10!nx01.iad01.newshosting.com!newshosting.com!69.28.186.77.MISMATCH!hwmnpeer03.lga!hwmnpeer01.lga!news.highwinds-media.com!hw-filter.lga!newsfe02.lga.POSTED!53ab2750!not-for-mail
From: "Tom St Denis" <tomstdenis@gmail.com>
Message-ID: <5343933426.232432.174942@50g2000cwy.googlegroups.com>
Newsgroups: bit.listserv.test
Subject: Shamir's Trick (EC-DSA verify)
Approved: "Tom St Denis" <tomstdenis@gmail.com>
Organization: http://groups.google.com
X-NNTP-Posting-Host: 74.104.204.117
Mime-Version: 1.0
Content-Type: text/plain; charset="iso-8859-1"
Complaints-To: groups-abuse@google.com
X-Trace-Info: posting.google.com 8168596750 87483 74.104.204.117 (3 Dec 2006 04:17:12 GMT)
User-Agent: G2/1.0
X-HTTP-UserAgent: Mozilla/5.0 (X11; U; Linux x86_64; en-US; rv:1.8.0.7) Gecko/20061009 SeaMonkey/1.0.5,gzip(gfe),gzip(gfe)
Injection-Info: 84g2000cwy.googlegroups.com; posting-host=74.104.204.117; posting-account=v6xdSg0AAAD63tq-yRAAhvNtO5tjUP7G
X-Link: http://libtomcrypt.org/
Lines: 40
X-Trace: nphhjmdkmllhpdkekannfilpcpbbolnmenpddmdgbmcljolajlfeibpefnflodnmoeempggdklbeniaablmlmenfbahapdkkankbcoajbmhacoifooihmbobmmjpaggoenfnojecgjgcfcij
NNTP-Posting-Date: Sat, 02 Dec 2006 21:51:02 MST
Date: Sun, 3 Dec 2006 04:17:12 GMT