From msuinfo!agate!howland.reston.ans.net!EU.net!Germany.EU.net!netmbx.de!zib-berlin.de!news.th-darmstadt.de!terra.wiwi.uni-frankfurt.de!zeus.rbi.informatik.uni-frankfurt.de!news.dfn.de!news.belwue.de!news.uni-stuttgart.de!rz.uni-karlsruhe.de!not-for-mail Wed Mar 30 11:41:20 1994 Path: msuinfo!agate!howland.reston.ans.net!EU.net!Germany.EU.net!netmbx.de!zib-berlin.de!news.th-darmstadt.de!terra.wiwi.uni-frankfurt.de!zeus.rbi.informatik.uni-frankfurt.de!news.dfn.de!news.belwue.de!news.uni-stuttgart.de!rz.uni-karlsruhe.de!not-for-mail From: S_JUFFA@IRAV1.ira.uka.de (|S| Norbert Juffa) Newsgroups: comp.lsi Subject: SUMMARY: Xilinx FPGAs and cryptographic algorithms Date: 29 Mar 1994 16:50:29 GMT Organization: University of Karlsruhe, FRG Lines: 416 Distribution: world Message-ID: <2n9m8l$ack@nz12.rz.uni-karlsruhe.de> NNTP-Posting-Host: irav1.ira.uka.de Mime-Version: 1.0 Content-Type: text/plain; charset=iso-8859-1 Content-Transfer-Encoding: 8bit X-News-Reader: VMS NEWS 1.25 Recently, I have been asking questions on the net regarding literature on HW design with FPGAs and the applicability of FPGAs to the implementation of cryptographic algorithms. This is a summary of the information I have received and that I figured out myself in the mean time. This article will be sent to the newsgroup comp.lsi and to the Xilinx Users mailing list. Thanks for their replies to: Herman Schmit (herman@amc.ece.cmu.edu), Brad Hutchings (hutch@timp.ee.byu.edu), Chi-Ping Hsu (qcktrn!chip%qcktrn@uunet.UU.NET), Joe Varghese (varghese@qcktrn.com), Philip Freidin (philip@magrathea.xilinx.com), Rick Barth (barth@rambus.com), Neil Bergmann (neil@jrc.flinders.edu.au), Norman Chan (nchan@crusader.xilinx.com), Mark Shand (shand@prl.dec.com) I apologize to any person that send me a message but that I forgot to include in the above list. With regard to general design questions when designing with FPGAs, there are two new books out: Stephen Trimberger, ed. "Field-Programmable Gate Array Technology" Kluwer Academic Publishers, 1994 Jesse Jenkins "Designing with FPGAs and CPLDs" Prentice Hall ISBN 0-13-721549-5 I aquired the later book from Computer Literacy Bookstores (Cupertino, Sunnyvale, San Jose, CA) for US$ 45. I haven't taken a look at it yet, so I can't say whether it is good or not. I discovered that there is a mailing list for people using or being interested in Xilinx products. It can be reached at XILINX-USERS@SANDIA.GOV. To be added to the list, send an email to XILINX-USERS-REQUEST@SANDIA.GOV with the line LIST:ADD. The feedback from this list seems to be far better than from comp.lsi In particular, Xilinx staff seems to read the messages there quite regularly. There is an international workshop dealing exclusively with FPGAs: 1st International Workshop on Field Programmable Gate Arrays, Feb. 16-18, 1992, Berkeley, CA Field-Programmable Gate Arrays: Architectures and Tools for Rapid Prototyping. Second International Workshop on Field Programmable Logic and Applications. Sorry, but the reference to the 2nd workshop is incomplete. There was also a workshop in 1993, for which I don't have the reference, and there is one coming up this year. The people at DEC's Paris Research Laboratory have done fast implementations of RSA (among other algorithms) on their PAM (programmable active memories). These are basically configurable matrices of Xilinx FPGAs. There are two research reports available via anonymous ftp to gatekeeper.pa.dec.com on these implementations. The files are in /pub/DEC/PRL/research-reports: Report 3: Bertin, P.; Roncin, D.; Vuillemin, J.: Introduction to Programmable Active Memories. June 1989 Report 4: Bertin, P.; Roncin, D.; Vuillemin, J.: Programmable Active Memories a Performance Assessment. March 1993 The first arcticle has also been published in: "Systolic Array Processors" (ed. McCanny, J.; McWhirter, J.; Swartzlander, E.), pp. 301-309 (1989) The second article was also published in: Parallel Architectures and Their Efficient Use. Proceedings First Heinz Nixdorf Symposium, Paderborn, Germany, Nov. 11-13, 1992 For those who have not access to ftp, there is also a automated mail server at DEC PRL. Try sending an email message with the subject line "help" to doc-server@prl.dec.com. Two other conference papers by the PRL group are: Shand, M.; Bertin, P.; Vuillemin, J.: "Hardware speedups in Long Integer Multiplication". Proceedings 2nd Annual ACM symposium on Parallel Algorithms and Architectures, July 2-6, 1990, Crete, Greece, pp. 138-145 Reprinted in ACM Computer Architecture News Vol. 10, No. 1, March 1991, pp. 106-113 Shand, M.; Vuillemin, J.: "Fast Implementations of RSA Cryptography" Proceedings 11th Symposium on Computer Arithmetic, June 29-July 2, 1993, Windsor, Ontario, pp 252-259 There is an architecture called SPLASH, which is a linear logic array built from Xilinx FPGAs. It was used to solve gene matching problems, but it could probably also be used for cryptographic algorithms. It is described in Waugh, T.C.: Field Programmable Gate Arrays Key to Reconfigurable Array Outperforming Supercomputers. Proceedings IEEE 1991 Custom Integrated Circuits Conference, San Diego, CA, USA, 12-15 May 1991, p 6.6/1-4 I have also received messages about successful implementations of DES on Xilinx FPGAs, both the 3000 and the 4000 series. -- Norbert Juffa (juffa@ira.uka.de) Appended are the email replies I received in reply to my questions: From: Herman Schmit The official DES documentation states that no software implementation of the DES is acceptably secure. I'm no security expert, but perhaps that's the reason that no one has commercially done DES on an FPGA. I guess the configuration bitstream for an FPGA could be broken into and compromised. We have been experimenting with high-level synthesis and FPGAs, and have played around with the DES. We've found that its really easy and efficient to implement the cypher function on a 4000 series FPGA. Basically this function, which is the core of the DES (I think its used 16 times in the DES) can be implemented just a couple of CLBs and a lot of routing sources. I'm sure that the whole DES could fit onto a single relatively small FPGA, and a large FPGA could probably be pretty highly pipelined. herman ------------------------------------------------------------------------------- From: Brad Hutchings Subject: Implementing crypto algorithms on Xilinx? Content-Length: 465 Hi, It has been done. The people at the Paris Digital Research Lab built something (it was based on the PERL board and was a lot faster than any other known supercomputer implementation) In addition, I have a student who is nearly finished with with a DES engine on Xilinx 3000 parts. Actually, FPGAs seem to be a good fit with encryption. Brad L. Hutchings Asst. Professor Dept. of Electrical and Computer Engineering Brigham Young University hutch@ee.byu.edu ------------------------------------------------------------------------------- From: qcktrn!chip%qcktrn@uunet.UU.NET ( Chi-Ping Hsu ) Subject: Re: Implementing crypto algorithms on Xilinx? The type of application can be emulated using Quickturn Emulation Systems easily. You can consider using Quickturn Box as if it is a very large FPGA. Since more and more people are starting to use ASIC emulation technology for algorithm verification, I thought you would like to know. Chi-Ping Hsu R&D Director Quickturn Design Systems ------------------------------------------------------------------------------- From: varghese@qcktrn.com ( Joe Varghese ) Reply-To: varghese@qcktrn.com Postal-Address: Quickturn Design Systems, 440 Clyde Avenue, Mountain View, CA 94043 Telephone: (415) 694 6671 Subject: Implementing crypto algorithms on Xilinx? I'm sure you will get a lot of responses to this one but just in case you haven't -- the people at DEC Paris Labs have done a lot of work in this area and they implemented the RSA encryption algorithm on their machine and they have phenomenal results. Here is a reference: P. Bertin, et. al. "Introduction to Programmable Active Memories", DEC Paris Laboratory, Technical Report 3, 1989. I'm sure that people at the Supercomputing Research Center (SRC) and other places have also tried various algorithms on their Splash architecture. There is a whole workshop devoted to this and related areas --- IEEE Workshop on FPGA's for Custom Computing Machines. ------------ Joe Varghese varghese@qcktrn.com ------------------------------------------------------------------------------- From: barth@rambus.com (Rick Barth) Subject: Implementing crypto algorithms on Xilinx? Try DEC Paris Research Laboratory Technical Reports. Send a message whose subject line is help to doc-server@prl.dec.com. Try Research Report #24. Subject: Re: Implementing crypto algorithms on Xilinx? From: neil@jrc.flinders.edu.au See Report #24 which describes RSA on XILINX. Neil Bergmann CSIRO/Flinders Joint Research Centre in Information Technology, Flinders University, GPO Box 2100, Adelaide SA 5001, AUSTRALIA Phone: +61 - 8 201 3113 Fax: + 61 - 8 201 3507 E-mail: neil@jrc.flinders.edu.au Index of reports from DECPRL archive service (updated Feb 22 13:43 reports/Index) - ----------------------------------------------------------------- _______________________________________________________________ Paris Research Laboratory Research Reports Index _______________________________________________________________ This is the list of Research Reports published by the Paris Research Laboratory (Digital Equipment Corporation). Both paper and online version can be ordered through this doc-server. -Paper versions are ordered with a "order" command. -Electronic versions are ordered with a "send " command -Electronic versions can be ftped from gatekeeper.pa.dec.com The files are in pub/DEC/PRL/research-reports. They are PostScript compressed. Paper Version ------------- Paper version of document are ordered with an "order" command. If you wish to receive a printed version of one of these reports, send an electronic message to: doc-server@prl.dec.com or decprl::doc-server whose subject line is : "order report ..." Enter your postal mail address in body message. The librarian will handle your request and send you the article you're asking for. Electronic Version ------------------ FTP Information: ============ These files are also available on gatekeeper.dec.com (login anonymous) in the directory pub/DEC/PRL/research-reports. They are in PostScript compressed format. DOC-SERVER Information: ====================== If you wish to receive by electronic mail any of these reports, write an electronic message to: doc-server@prl.dec.com or decprl::doc-server whose subject line is : "send report ..." Please, do not repeat in message body your command order. The doc-server will mail you back the report you ask for. You can receive abstracts for reports : mail doc-server a message whose subject is "send reports abstracts". Usually, you have choice between two files : - 'normal' size - 'large' . 'Normal' means the report is divided in few separate parts, (usually 3 to 8), whose size is under 100kb, to ensure correct transmission through all mail gateways. **'large' versions means a file containing the whole report.** File size is often over 200 ko. Many mail gateways bounce back after 100 ko or will not transmit more , due to mail limitations inherent to their network. **Please, choose this option after making sure your network** **configuration between PRL and your site allows such size.** _______________________________________________________________ Any further information can be obtained to: Librarian Digital Paris Research Laboratory 85 avenue Victor Hugo 92563 Rueil Malmaison FRANCE [...deleted...] _______________________________________________________________ PRL-RR-3 Research Report Number 3: Introduction to Programmable Active Memories. Patrice Bertin, Didier Roncin, and Jean Vuillemin. June 1989. Command for Online Version (3 parts) :send report 3 Command for Online Version (209 kb) :send report 3.ps Command for Printed Version :order report 3 [Please add your address in message] [...deleted...] _______________________________________________________________ PRL-RR-24 Research Report 24: Programmable Active Memories: a Performance Assessment. Patrice Bertin, Didier Roncin, and Jean Vuillemin. March 1993. Command for Online Version (6 parts) :send report 24 Command for Online Version (332 kb) :send report 24.ps Command for printed Version :order report 24 [Please add your address in message] _______________________________________________________________ ------------------------------------------------------------------------------- From: Norman Chan Norbert, The folks at DEC wrote an article that presents quantitative performance measurements for the computing power of Programmable Active Memories or PAM. The name of the article is Programmable Active Memories: a Performance Assessment, and it is based on Programmable Gate Array technology. It includes 10 PAM applications and RSA cryptography is one of them. I'll be willing to fax you a copy of it if you email me your fax number. Also, Steve Trimberger at Xilinx recently completed a book on FPGAs thatincludes architecture, software and applications discussions of SRAM, Antifuse and EPLD-style FPGAs. Chapters were written by people from Xilinx, Actel and Altera. The book is: "Field-Programmable Gate Array Technology," Stephen Trimberger, ed., Kluwer Academic Publishers, 1994. If you are interested, please contact: Email: kluwer@world.std.com Phone: USA-617-871-6600 or Netherlands (0)78-524400 Fax: USA-617-871-6528 or Netherlands (0)78-524474 Jesse Jenkins at Xilinx also wrote a book titled "Designing with FPGAs and EPLDs" and is published by Prentice-Hall. The ISBN number is 0-13-721549-5. It is available in several technical bookstores (locally at Computer Literacy). Prentice-Hall can be contacted at 1-800-223-1360 for more information. It includes twelve chapters and describes architectures and appropriate design techniques for most commercially available products as well as critical architecture needs and design software capabilities. Jesse uses it to teach at Santa Clara, Berkeley extension, and Santa Cruz extension. Hope this helps. Regards, ============================================ / /\/ / Norman Chan \ \ \/ nchan@xilinx.com \ \ Xilinx, Inc. / / 2100 Logic Drive / / / \ San Jose, CA 95124 \_\/ \_\ (408)559-7778 FAX: 408-879-4442 ============================================ ------------------------------------------------------------------------------- From: shand@prl.dec.com Look at: "Hardware speedups in Long Integer Multiplication" M. Shand, P. Bertin, J. Vuillemin Proceedings of 2nd Annual ACM Symposium on Parallel Algorithms and Architectures, pp 138-145 July 2-6 1990 Crete, Greece Reprinted in ACM Computer Architecture News Vol. 10, No. 1 March 1991 pp 106-113 And "Fast Implementations of RSA Cryptography", M. Shand, J. Vuillemin Proceedings of 11th Symposium on Computer Arithmetic Jne 29-July 2, 1993 Windsor, Ontario pp 252-259 I will send you the postscript of this second paper in a separate message. Mark Shand