Path: news1.icaen!news.uiowa.edu!chi-news.cic.net!portc01.blue.aol.com!portc02.blue.aol.com!howland.erols.net!worldnet.att.net!cpk-news-hub1.bbnplanet.com!cam-news-hub1.bbnplanet.com!news.bbnplanet.com!uunet!in2.uu.net!128.6.21.17!dziuxsolim.rutgers.edu!pilot.njin.net!not-for-mail From: comp-sources-apple2@pilot.njin.net Newsgroups: comp.sources.apple2 Subject: v001SRC104: idea -- IDEA Cipher in 65C02 Assembly Language Date: 17 Feb 1997 14:32:29 -0500 Organization: Rutgers University Lines: 371 Sender: jac@pilot.njin.net Approved: jac@pilot.njin.net Message-ID: <5eabod$1l2@pilot.njin.net> NNTP-Posting-Host: pilot.njin.net Submitted-by: Matthew Fischer (mfischer@blue.weeg.uiowa.edu) Posting-number: Volume 1, Source 104 Archive-name: library/asm/crypto/idea Architecture: ANY_2 Version-number: 1.4 idea This package implements the International Data Encryption Algorithm (IDEA) block cipher in 65C02 assembly language. The IDEA cipher algorithm was developed by Xuejia Lai and James L. Massey, of ETH Zurich. Note: This package requires a 65C02. WARNING: Because of United States Government regulations regarding distribution of cryptography, no source code is included in this package. Only the Read.Me file is included. To obtain the actual source code, please access the comp.sources.apple2 web page at: http://www.openix.com/~jac You can find it in the "crypto" section (by topic) or as Posting Number 104 (by list) or as: ftp://ftp.openix.com/ftp/jac/comp.sources.apple2/src/source.104.gz You may download the source code ONLY if you are physically residing in the United States of America and allowed to do so by United States law. This code is not to be made available to foreign nationals or their agents. As always, packed in AAF. Enjoy. ******************************************************************************** The full comp.sources.apple2 archives, including a tool to unpack the AAF archive format, are available at: http://www.openix.com/~jac You can also ftp them from: ftp://ftp.openix.com/ftp/jac/comp.sources.apple2/* ftp://ftp.sterling.com/usenet/comp.sources.apple2/* The web page will likely be the easiest way to download them. Questions or comments to: jac@openix.com ******************************************************************************** =Manifest -Manifest -Read.Me =Read.Me - -idea - -This package implements the International Data Encryption Algorithm -(IDEA) block cipher in 65C02 assembly language. The IDEA cipher -algorithm was developed by Xuejia Lai and James L. Massey, of ETH -Zurich. - -Note: This package requires a 65C02. - -====================================================================== -WARNING about Exporting this Package from the United States of America -====================================================================== -The United States Government has determined that certain types of -cryptographic technology are "munitions" and has made it illegal to -export them. Because the legality of export is determined by the -policies of the United States Government's State Department, and not as -a matter of statute, it can be difficult to determine exactly when -cryptographic technology can be exported from the United States. The -rules, in fact, are constantly changing. - -While one might think that export restrictions do not apply because the -IDEA cipher was developed in Switzerland and software implementing it -is freely available outside the United States, it is not clear whether -or not export is prohibited. As this information is not known to the -author, he will not export this software nor will he assist those -interested in doing so. - -Some less enlightened countries impose serious penalties on their -citizens who use cryptography. In some countries the penalties for -doing so are long prison terms and fines. - -The user takes all responsibility for exporting, importing, or using -this package, and for complying with local laws. - -======================= -IDEA Cipher Description -======================= -IDEA is what is known as a symmetric block cipher. The cipher uses a -128-bit key to encode a message, 64 bits at a time. The same key is -used to decode the encoded data back into the original message. - -A detailed description of the algorithm, including implementation -details, can be found at: - ftp://isibee.ethz.ch/pub/simpl/idea.V1.2.tar.Z - -(The paper "idea.ps" contained in this archive contains the information -used to create this implementation.) - -The IDEA cipher is patented and its use is subject to certain licensing -restrictions. This implementation as it stands does not require a -license because it is not an actual application. If you incorporate -these routines into an application that you intend to distribute (even -if it is freeware), you will need to get a license. Included here is -the notice that is to be added to freeware products containing the -cipher, to give you an idea of what types of restrictions there are: - - This Software/Hardware product contains the algorithm IDEA as - described and claimed in US Patent No. 5,214,703, EPO Patent - No. 0482154 and filed Japanese Patent Application No. - 508119/1991 "Device for the conversion of a digital block and - use of same" (hereinafter referred to as "Algorithm"). Any use - of the Algorithm for Commercial Purposes is thus subject to a - license from Ascom Systec Ltd. of CH-5506 Maegenwil - (Switzerland), being the patentee and sole owner of all rights, - including the term IDEA. - - Commercial Purposes shall mean any revenue generating purpose - including but not limited to - - i) using the Algorithm for company internal purposes - (subject to a Site License). - - ii) incorporating an application software containing - the Algorithm into any hardware and/or software and - distributing such hardware and/or software and/or - providing services related thereto to others (subject - to a Product License). - - iii) using a product containing an application software - that uses the Algorithm (subject to an End-User - License), except in case where such End-User has - acquired an implied license by purchasing the said - product from an authorized licensee or where the - End-User has already signed up for a Site License. - - All such commercial license agreements are available - exclusively from Ascom Systec Ltd. and may be requested via the - Internet World Wide Web at http://www.ascom.ch/systec or by - sending an electronic mail to IDEA@ascom.ch. Any misuse will be - prosecuted. - - Use other than for Commercial Purposes is strictly limited to - data transfer between private individuals and not serving - Commercial Purposes. The use by government agencies, non-profit - organizations etc. is considered as use for Commercial Purposes - but may be subject to special conditions. Requests for waivers - for non-commercial use (e.g. by software developers) are - welcome. - -========= -Internals -========= -A detailed description of the IDEA cipher can be found in the -aforementioned paper, and the reader is referred there for details. -This assembly implementation is basically a translation of the C code -given in the paper, with a few optimizations. The paper makes good -documentation for this implementation of the routine. - -The remainder of this section describes implementation details largely -specific to the Apple //. - -All integers are unsigned, and the order of bytes in a word or longword -is least significant byte first and most significant byte last. More -specifically, a 16-bit word is: - +-----+-----+ - | LSB | MSB | - +-----+-----+ -and a 32-bit longword is: - +-----+-----+-----+-----+ - | LSW | MSW | - +-----+-----+-----+-----+ - -This is the standard Apple // representation for integers. Thus, it -should not be difficult to convert this code into 65816 native code in -order to take advantage of the 16-bit operations provided by the -65816. - -There are two exceptions to this byte ordering, which can be -confusing. These exceptions arise from the need for the IDEA cipher to -interpret strings of bytes as strings of words, because the cipher is -designed around 16-bit arithmetic. The 128-bit user key must be broken -up into eight 16-bit words, and the 64-bit message blocks must be -broken into four 16-bit words. - -Because the key and data values could come from non-Apple machines, -there is no way to know, a priori, the byte order used by that machine. -To eliminate portability problems, words are always interpreted as -having the most significant byte first and the least significant byte -last. This is a convention adopted by the cipher's designers. - -Using this byte ordering for interchange between machines makes it -possible to transfer data encrypted with the Apple // subroutines -between different types of computers and encrypt/decrypt without any -problems. This problem is not specific to the Apple //; the Intel -80x86 and the Motorola 680x0, for example, use a different byte -ordering, and so a machine independent ordering is needed. - ------------------------------------------ -General Encryption/Decryption Information ------------------------------------------ -The CIP routines encrypts or decrypts, depending upon which kind of key -schedule is stored at Z, the 8-byte buffer specified by PTR. The -original data in the buffer is replaced with the encrypted or decrypted -result, depending upon the operation being performed. - ----------- -Encryption ----------- -The KEY routine creates the encryption key schedule. The 128-bit user -key at USK is processed as eight 16-bit unsigned integers, with the MSB -coming first. In other words, USK[0] is the MSB and USK[15] is the -LSB. The resulting key schedule is stored at Z. - -To encrypt the data in the buffer, the process is: - + store the 16-byte user key at USK - + call KEY - + call CIP - ----------- -Decryption ----------- -To decrypt the data in the buffer, the process is: - + store the 16-byte user key at USK - + call KEY - + call DEK - + copy DEK to Z - + call CIP - -The DEK routine creates the decryption key schedule by inverting the -encryption key schedule. The 104-byte block at Z, as created by KEY, -is processed and stored at DK. For the CIP routine to be able to use -it, it should be copied into the block at Z. - -The author chose not to have this copy done automatically by DEK, -because depending on the application of this package, it may be -desirable to have both the encryption key schedule and the decryption -key schedule available at the same time. - ---------------------- -Configuration for Use ---------------------- -This package implements the IDEA encryption algorithm and calculates -its key schedules. To use these subroutines to encrypt data, you will -need to include them in another program. Details on passing arguments -to the subroutines are given in the source. - -The following variables are used by this package: - - Name Purpose - ---- -------------------------------- - USK 16-byte user key - Z 104-byte key schedule - DK 104-byte decryption key schedule - PTR pointer to 8-byte data block - X1 first word of 8-byte block - X2 second word of 8-byte block - X3 third word of 8-byte block - X4 fourth word of 8-byte block - X2B temp copy of X2 used by CIP - T1 temp word used by CIP - T2 temp word used by CIP - B1 temp integer used by INV - B2 temp integer used by INV - N1 first operand for MML and MUL - N2 second operand for MML and MUL - RES result of MML and MUL - M1 first operand for DIV - M2 second operand for DIV - REM remainder of DIV - -The PTR location contains the address of the 8-byte block to be -encrypted or decrypted. It must be stored as two adjacent bytes -somewhere on the zero page, because the CIP routine refers to the data -block through it by the 6502's Indirect Indexed addressing mode. - -It is a good idea to find some place on the zero page to put X1 through -X4, and N1, N2, and RES, etc. The routines that use these data areas -will work fine as is, but they will be much faster if their variables -can be moved onto the zero page. The author did not specify fixed zero -page locations because free zero page locations can vary among -applications/environments. - -If X1, X2, X3, and X4 are moved to a different location, please note -that they must always be stored in adjacent memory locations. - --------------- -Other Routines --------------- -The MML routine performs multiplication modulo 65537. The 16-bit -unsigned integer at N1 is multiplied by the 16-bit unsigned integer at -N2, and the 16-bit unsigned integer product is stored at RES. MML is -called by CIP. - -The MUL16 routine performs 16-bit multiplication. The 16-bit unsigned -integers N1 and N2 are multiplied, and the 32-bit unsigned integer -product is stored at RES. MUL16 is called by MML. - -The INV routine calculates multiplicative inverses modulo 65537, using -Euclid's GCD algorithm. The 16-bit unsigned integer at M2 is inverted -and stored at B1 as a 16-bit unsigned integer. INV is called by DEK. - -The MUL routine performs 24-bit multiplication. The 24-bit unsigned -integers at N1 and N2 are multiplied, and the 24-bit unsigned integer -product is stored at RES. MUL is called by INV. - -The DIV routine performs 24-bit division. The 24-bit unsigned integer -at N1 is divided by the unsigned integer at N2. The 24-bit unsigned -integer quotient is stored at N1, and the 24-bit unsigned integer -remainder is stored at RES. DIV is called by INV. - -========== -Assembling -========== -This package assembles with the Merlin assembler. It was developed -using Merlin-8, version 2.58. While it may be possible to assemble -this code with other assemblers, the author has not done so and is -unaware of the details involved in doing so. - -The source is provided in two formats. idea.merlin.s is a binary -source file suitable for loading directly into the Merlin assembler. -idea.s is a text version of the same source, which is intended to be -human readable and is perhaps more suitable for porting to other -assemblers besides Merlin. - -===== -Files -===== -The following files are present in this package - Read.Me This file - idea.merlin.bsc idea.merlin.s, BinSCII encoded for - transmission - idea.s Human readable copy of idea.merlin.s - -You will need to decode idea.merlin.bsc using BinSCII in order to -produce the file idea.merlin.s, which can be loaded into Merlin -directly. - -========= -Copyright -========= -Copyright 1995-1997 by Matthew Fischer - -This package is freeware. - -================== -Author Information -================== -Matthew Fischer -mfischer@blue.weeg.uiowa.edu - -Version 1.4 -January 1997 + END OF ARCHIVE