요약·해설과 원문, 전문 번역을 서로 분리했습니다. API 이름, symbol, source path는 원문 표기를 사용합니다.
1. 요약·해설
원문의 핵심 논리와 kernel programming 관점의 보충 설명입니다. 아래의 전문 번역과는 별도로 작성했습니다.
2. 영어 원문 전체
번역 기준이 된 Linux v6.18.37 원문입니다. 줄 번호는 이 버전의 파일 좌표입니다.
원문 전체 펼치기
.. SPDX-License-Identifier: GPL-2.0
.. include:: <isonum.txt>
===========================================
Fast & Portable DES encryption & decryption
===========================================
.. note::
Below is the original README file from the descore.shar package,
converted to ReST format.
------------------------------------------------------------------------------
des - fast & portable DES encryption & decryption.
Copyright |copy| 1992 Dana L. How
This program is free software; you can redistribute it and/or modify
it under the terms of the GNU Library General Public License as published by
the Free Software Foundation; either version 2 of the License, or
(at your option) any later version.
This program is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
GNU Library General Public License for more details.
You should have received a copy of the GNU Library General Public License
along with this program; if not, write to the Free Software
Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
Author's address: how@isl.stanford.edu
.. README,v 1.15 1992/05/20 00:25:32 how E
==>> To compile after untarring/unsharring, just ``make`` <<==
This package was designed with the following goals:
1. Highest possible encryption/decryption PERFORMANCE.
2. PORTABILITY to any byte-addressable host with a 32bit unsigned C type
3. Plug-compatible replacement for KERBEROS's low-level routines.
This second release includes a number of performance enhancements for
register-starved machines. My discussions with Richard Outerbridge,
71755.204@compuserve.com, sparked a number of these enhancements.
To more rapidly understand the code in this package, inspect desSmallFips.i
(created by typing ``make``) BEFORE you tackle desCode.h. The latter is set
up in a parameterized fashion so it can easily be modified by speed-daemon
hackers in pursuit of that last microsecond. You will find it more
illuminating to inspect one specific implementation,
and then move on to the common abstract skeleton with this one in mind.
performance comparison to other available des code which i could
compile on a SPARCStation 1 (cc -O4, gcc -O2):
this code (byte-order independent):
- 30us per encryption (options: 64k tables, no IP/FP)
- 33us per encryption (options: 64k tables, FIPS standard bit ordering)
- 45us per encryption (options: 2k tables, no IP/FP)
- 48us per encryption (options: 2k tables, FIPS standard bit ordering)
- 275us to set a new key (uses 1k of key tables)
this has the quickest encryption/decryption routines i've seen.
since i was interested in fast des filters rather than crypt(3)
and password cracking, i haven't really bothered yet to speed up
the key setting routine. also, i have no interest in re-implementing
all the other junk in the mit kerberos des library, so i've just
provided my routines with little stub interfaces so they can be
used as drop-in replacements with mit's code or any of the mit-
compatible packages below. (note that the first two timings above
are highly variable because of cache effects).
kerberos des replacement from australia (version 1.95):
- 53us per encryption (uses 2k of tables)
- 96us to set a new key (uses 2.25k of key tables)
so despite the author's inclusion of some of the performance
improvements i had suggested to him, this package's
encryption/decryption is still slower on the sparc and 68000.
more specifically, 19-40% slower on the 68020 and 11-35% slower
on the sparc, depending on the compiler;
in full gory detail (ALT_ECB is a libdes variant):
=============== ============== =============== =================
compiler machine desCore libdes ALT_ECB slower by
=============== ============== =============== =================
gcc 2.1 -O2 Sun 3/110 304 uS 369.5uS 461.8uS 22%
cc -O1 Sun 3/110 336 uS 436.6uS 399.3uS 19%
cc -O2 Sun 3/110 360 uS 532.4uS 505.1uS 40%
cc -O4 Sun 3/110 365 uS 532.3uS 505.3uS 38%
gcc 2.1 -O2 Sun 4/50 48 uS 53.4uS 57.5uS 11%
cc -O2 Sun 4/50 48 uS 64.6uS 64.7uS 35%
cc -O4 Sun 4/50 48 uS 64.7uS 64.9uS 35%
=============== ============== =============== =================
(my time measurements are not as accurate as his).
the comments in my first release of desCore on version 1.92:
- 68us per encryption (uses 2k of tables)
- 96us to set a new key (uses 2.25k of key tables)
this is a very nice package which implements the most important
of the optimizations which i did in my encryption routines.
it's a bit weak on common low-level optimizations which is why
it's 39%-106% slower. because he was interested in fast crypt(3) and
password-cracking applications, he also used the same ideas to
speed up the key-setting routines with impressive results.
(at some point i may do the same in my package). he also implements
the rest of the mit des library.
(code from eay@psych.psy.uq.oz.au via comp.sources.misc)
fast crypt(3) package from denmark:
the des routine here is buried inside a loop to do the
crypt function and i didn't feel like ripping it out and measuring
performance. his code takes 26 sparc instructions to compute one
des iteration; above, Quick (64k) takes 21 and Small (2k) takes 37.
he claims to use 280k of tables but the iteration calculation seems
to use only 128k. his tables and code are machine independent.
(code from glad@daimi.aau.dk via alt.sources or comp.sources.misc)
swedish reimplementation of Kerberos des library
- 108us per encryption (uses 34k worth of tables)
- 134us to set a new key (uses 32k of key tables to get this speed!)
the tables used seem to be machine-independent;
he seems to have included a lot of special case code
so that, e.g., ``long`` loads can be used instead of 4 ``char`` loads
when the machine's architecture allows it.
(code obtained from chalmers.se:pub/des)
crack 3.3c package from england:
as in crypt above, the des routine is buried in a loop. it's
also very modified for crypt. his iteration code uses 16k
of tables and appears to be slow.
(code obtained from aem@aber.ac.uk via alt.sources or comp.sources.misc)
``highly optimized`` and tweaked Kerberos/Athena code (byte-order dependent):
- 165us per encryption (uses 6k worth of tables)
- 478us to set a new key (uses <1k of key tables)
so despite the comments in this code, it was possible to get
faster code AND smaller tables, as well as making the tables
machine-independent.
(code obtained from prep.ai.mit.edu)
UC Berkeley code (depends on machine-endedness):
- 226us per encryption
- 10848us to set a new key
table sizes are unclear, but they don't look very small
(code obtained from wuarchive.wustl.edu)
motivation and history
======================
a while ago i wanted some des routines and the routines documented on sun's
man pages either didn't exist or dumped core. i had heard of kerberos,
and knew that it used des, so i figured i'd use its routines. but once
i got it and looked at the code, it really set off a lot of pet peeves -
it was too convoluted, the code had been written without taking
advantage of the regular structure of operations such as IP, E, and FP
(i.e. the author didn't sit down and think before coding),
it was excessively slow, the author had attempted to clarify the code
by adding MORE statements to make the data movement more ``consistent``
instead of simplifying his implementation and cutting down on all data
movement (in particular, his use of L1, R1, L2, R2), and it was full of
idiotic ``tweaks`` for particular machines which failed to deliver significant
speedups but which did obfuscate everything. so i took the test data
from his verification program and rewrote everything else.
a while later i ran across the great crypt(3) package mentioned above.
the fact that this guy was computing 2 sboxes per table lookup rather
than one (and using a MUCH larger table in the process) emboldened me to
do the same - it was a trivial change from which i had been scared away
by the larger table size. in his case he didn't realize you don't need to keep
the working data in TWO forms, one for easy use of half the sboxes in
indexing, the other for easy use of the other half; instead you can keep
it in the form for the first half and use a simple rotate to get the other
half. this means i have (almost) half the data manipulation and half
the table size. in fairness though he might be encoding something particular
to crypt(3) in his tables - i didn't check.
i'm glad that i implemented it the way i did, because this C version is
portable (the ifdef's are performance enhancements) and it is faster
than versions hand-written in assembly for the sparc!
porting notes
=============
one thing i did not want to do was write an enormous mess
which depended on endedness and other machine quirks,
and which necessarily produced different code and different lookup tables
for different machines. see the kerberos code for an example
of what i didn't want to do; all their endedness-specific ``optimizations``
obfuscate the code and in the end were slower than a simpler machine
independent approach. however, there are always some portability
considerations of some kind, and i have included some options
for varying numbers of register variables.
perhaps some will still regard the result as a mess!
1) i assume everything is byte addressable, although i don't actually
depend on the byte order, and that bytes are 8 bits.
i assume word pointers can be freely cast to and from char pointers.
note that 99% of C programs make these assumptions.
i always use unsigned char's if the high bit could be set.
2) the typedef ``word`` means a 32 bit unsigned integral type.
if ``unsigned long`` is not 32 bits, change the typedef in desCore.h.
i assume sizeof(word) == 4 EVERYWHERE.
the (worst-case) cost of my NOT doing endedness-specific optimizations
in the data loading and storing code surrounding the key iterations
is less than 12%. also, there is the added benefit that
the input and output work areas do not need to be word-aligned.
OPTIONAL performance optimizations
==================================
1) you should define one of ``i386,`` ``vax,`` ``mc68000,`` or ``sparc,``
whichever one is closest to the capabilities of your machine.
see the start of desCode.h to see exactly what this selection implies.
note that if you select the wrong one, the des code will still work;
these are just performance tweaks.
2) for those with functional ``asm`` keywords: you should change the
ROR and ROL macros to use machine rotate instructions if you have them.
this will save 2 instructions and a temporary per use,
or about 32 to 40 instructions per en/decryption.
note that gcc is smart enough to translate the ROL/R macros into
machine rotates!
these optimizations are all rather persnickety, yet with them you should
be able to get performance equal to assembly-coding, except that:
1) with the lack of a bit rotate operator in C, rotates have to be synthesized
from shifts. so access to ``asm`` will speed things up if your machine
has rotates, as explained above in (3) (not necessary if you use gcc).
2) if your machine has less than 12 32-bit registers i doubt your compiler will
generate good code.
``i386`` tries to configure the code for a 386 by only declaring 3 registers
(it appears that gcc can use ebx, esi and edi to hold register variables).
however, if you like assembly coding, the 386 does have 7 32-bit registers,
and if you use ALL of them, use ``scaled by 8`` address modes with displacement
and other tricks, you can get reasonable routines for DesQuickCore... with
about 250 instructions apiece. For DesSmall... it will help to rearrange
des_keymap, i.e., now the sbox # is the high part of the index and
the 6 bits of data is the low part; it helps to exchange these.
since i have no way to conveniently test it i have not provided my
shoehorned 386 version. note that with this release of desCore, gcc is able
to put everything in registers(!), and generate about 370 instructions apiece
for the DesQuickCore... routines!
coding notes
============
the en/decryption routines each use 6 necessary register variables,
with 4 being actively used at once during the inner iterations.
if you don't have 4 register variables get a new machine.
up to 8 more registers are used to hold constants in some configurations.
i assume that the use of a constant is more expensive than using a register:
a) additionally, i have tried to put the larger constants in registers.
registering priority was by the following:
- anything more than 12 bits (bad for RISC and CISC)
- greater than 127 in value (can't use movq or byte immediate on CISC)
- 9-127 (may not be able to use CISC shift immediate or add/sub quick),
- 1-8 were never registered, being the cheapest constants.
b) the compiler may be too stupid to realize table and table+256 should
be assigned to different constant registers and instead repetitively
do the arithmetic, so i assign these to explicit ``m`` register variables
when possible and helpful.
i assume that indexing is cheaper or equivalent to auto increment/decrement,
where the index is 7 bits unsigned or smaller.
this assumption is reversed for 68k and vax.
i assume that addresses can be cheaply formed from two registers,
or from a register and a small constant.
for the 68000, the ``two registers and small offset`` form is used sparingly.
all index scaling is done explicitly - no hidden shifts by log2(sizeof).
the code is written so that even a dumb compiler
should never need more than one hidden temporary,
increasing the chance that everything will fit in the registers.
KEEP THIS MORE SUBTLE POINT IN MIND IF YOU REWRITE ANYTHING.
(actually, there are some code fragments now which do require two temps,
but fixing it would either break the structure of the macros or
require declaring another temporary).
special efficient data format
==============================
bits are manipulated in this arrangement most of the time (S7 S5 S3 S1)::
003130292827xxxx242322212019xxxx161514131211xxxx080706050403xxxx
(the x bits are still there, i'm just emphasizing where the S boxes are).
bits are rotated left 4 when computing S6 S4 S2 S0::
282726252423xxxx201918171615xxxx121110090807xxxx040302010031xxxx
the rightmost two bits are usually cleared so the lower byte can be used
as an index into an sbox mapping table. the next two x'd bits are set
to various values to access different parts of the tables.
how to use the routines
datatypes:
pointer to 8 byte area of type DesData
used to hold keys and input/output blocks to des.
pointer to 128 byte area of type DesKeys
used to hold full 768-bit key.
must be long-aligned.
DesQuickInit()
call this before using any other routine with ``Quick`` in its name.
it generates the special 64k table these routines need.
DesQuickDone()
frees this table
DesMethod(m, k)
m points to a 128byte block, k points to an 8 byte des key
which must have odd parity (or -1 is returned) and which must
not be a (semi-)weak key (or -2 is returned).
normally DesMethod() returns 0.
m is filled in from k so that when one of the routines below
is called with m, the routine will act like standard des
en/decryption with the key k. if you use DesMethod,
you supply a standard 56bit key; however, if you fill in
m yourself, you will get a 768bit key - but then it won't
be standard. it's 768bits not 1024 because the least significant
two bits of each byte are not used. note that these two bits
will be set to magic constants which speed up the encryption/decryption
on some machines. and yes, each byte controls
a specific sbox during a specific iteration.
you really shouldn't use the 768bit format directly; i should
provide a routine that converts 128 6-bit bytes (specified in
S-box mapping order or something) into the right format for you.
this would entail some byte concatenation and rotation.
Des{Small|Quick}{Fips|Core}{Encrypt|Decrypt}(d, m, s)
performs des on the 8 bytes at s into the 8 bytes at
``d. (d,s: char *)``.
uses m as a 768bit key as explained above.
the Encrypt|Decrypt choice is obvious.
Fips|Core determines whether a completely standard FIPS initial
and final permutation is done; if not, then the data is loaded
and stored in a nonstandard bit order (FIPS w/o IP/FP).
Fips slows down Quick by 10%, Small by 9%.
Small|Quick determines whether you use the normal routine
or the crazy quick one which gobbles up 64k more of memory.
Small is 50% slower then Quick, but Quick needs 32 times as much
memory. Quick is included for programs that do nothing but DES,
e.g., encryption filters, etc.
Getting it to compile on your machine
=====================================
there are no machine-dependencies in the code (see porting),
except perhaps the ``now()`` macro in desTest.c.
ALL generated tables are machine independent.
you should edit the Makefile with the appropriate optimization flags
for your compiler (MAX optimization).
Speeding up kerberos (and/or its des library)
=============================================
note that i have included a kerberos-compatible interface in desUtil.c
through the functions des_key_sched() and des_ecb_encrypt().
to use these with kerberos or kerberos-compatible code put desCore.a
ahead of the kerberos-compatible library on your linker's command line.
you should not need to #include desCore.h; just include the header
file provided with the kerberos library.
Other uses
==========
the macros in desCode.h would be very useful for putting inline des
functions in more complicated encryption routines.
3. 한국어 전문 번역
영어 원문의 문단 순서와 의미를 유지한 전체 번역입니다. 코드, 함수명, symbol과 URL은 원문 표기를 유지합니다.
빠르고 이식 가능한 DES 암호화·복호화
1-56SPDX 라이선스 식별자: `GPL-2.0`
빠르고 이식 가능한 DES 암호화·복호화
아래 내용은 `descore.shar` package의 원본 README를 ReST 형식으로 변환한 것입니다.
`des`: 빠르고 이식 가능한 DES 암호화·복호화
Copyright © 1992 Dana L. How
이 프로그램은 자유 software입니다. Free Software Foundation이 공표한 GNU Library General Public License version 2 또는 선택에 따라 그 이후 version의 조건에 따라 재배포하거나 수정할 수 있습니다.
이 프로그램은 유용하기를 바라며 배포하지만 어떠한 보증도 하지 않습니다. 상품성 또는 특정 목적 적합성에 대한 묵시적 보증도 없습니다. 자세한 내용은 GNU Library General Public License를 참조하십시오.
이 프로그램과 함께 GNU Library General Public License 사본을 받았어야 합니다. 받지 못했다면 Free Software Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA로 문의하십시오.
저자 주소: `how@isl.stanford.edu`
README revision: `1.15 1992/05/20 00:25:32 how E`
Archive를 푼 뒤 compile하려면 `make`만 실행하면 됩니다.
이 package의 설계 목표는 다음과 같습니다.
- 1. 가능한 최고의 암호화·복호화 성능
- 2. 32-bit unsigned C type을 갖고 byte 단위 주소 지정이 가능한 모든 host로의 이식성
- 3. KERBEROS 저수준 routine과 plug-compatible한 대체 구현
두 번째 release에는 register가 부족한 machine을 위한 여러 성능 개선이 포함되었습니다. Richard Outerbridge(`71755.204@compuserve.com`)와의 논의가 이러한 개선 중 여러 가지의 계기가 되었습니다.
Code를 더 빨리 이해하려면 `desCode.h`보다 먼저 `make`로 생성되는 `desSmallFips.i`를 살펴보십시오. `desCode.h`는 마지막 microsecond까지 줄이려는 개발자가 쉽게 수정할 수 있도록 parameter화되어 있습니다. 구체적인 구현 하나를 먼저 본 다음 이를 염두에 두고 공통 추상 골격으로 넘어가는 편이 이해하기 쉽습니다.
SPARCStation 1에서의 자체 성능
57-77SPARCStation 1에서 compile할 수 있었던 다른 DES code와의 성능 비교입니다. Compiler option은 `cc -O4`, `gcc -O2`입니다.
이 code는 byte order에 독립적이며 측정값은 다음과 같습니다.
- 암호화당 30 µs: 64K table, IP/FP 없음
- 암호화당 33 µs: 64K table, FIPS 표준 bit ordering
- 암호화당 45 µs: 2K table, IP/FP 없음
- 암호화당 48 µs: 2K table, FIPS 표준 bit ordering
- 새 키 설정 275 µs: 1K key table 사용
저자는 이것이 자신이 본 가장 빠른 암호화·복호화 routine이라고 설명합니다. 관심 대상이 `crypt(3)`나 password cracking이 아니라 빠른 DES filter였으므로 key 설정 routine 최적화는 아직 하지 않았습니다. MIT Kerberos DES library의 나머지를 다시 구현하는 대신 작은 stub interface를 제공하여 MIT code나 아래의 MIT 호환 package에 drop-in replacement로 쓸 수 있게 했습니다. 앞의 두 측정은 cache 영향으로 변동이 큽니다.
호주 Kerberos DES 대체 구현
78-119호주에서 만든 Kerberos DES 대체 구현 version 1.95의 측정값입니다.
- 암호화당 53 µs: 2K table 사용
- 새 키 설정 96 µs: 2.25K key table 사용
저자가 제안했던 성능 개선 일부가 포함되었지만 이 package의 암호화·복호화는 SPARC와 68000에서 여전히 더 느렸습니다. Compiler에 따라 68020에서 19~40%, SPARC에서 11~35% 느렸습니다. `ALT_ECB`는 libdes variant입니다.
| Compiler | Machine | desCore | libdes | ALT_ECB | 느린 비율 |
|---|---|---|---|---|---|
| gcc 2.1 -O2 | Sun 3/110 | 304 µs | 369.5 µs | 461.8 µs | 22% |
| cc -O1 | Sun 3/110 | 336 µs | 436.6 µs | 399.3 µs | 19% |
| cc -O2 | Sun 3/110 | 360 µs | 532.4 µs | 505.1 µs | 40% |
| cc -O4 | Sun 3/110 | 365 µs | 532.3 µs | 505.3 µs | 38% |
| gcc 2.1 -O2 | Sun 4/50 | 48 µs | 53.4 µs | 57.5 µs | 11% |
| cc -O2 | Sun 4/50 | 48 µs | 64.6 µs | 64.7 µs | 35% |
| cc -O4 | Sun 4/50 | 48 µs | 64.7 µs | 64.9 µs | 35% |
저자는 자신의 시간 측정이 상대 저자의 측정보다 정확하지 않다고 덧붙입니다.
desCore 첫 release에서 version 1.92에 관해 남긴 측정은 다음과 같습니다.
- 암호화당 68 µs: 2K table 사용
- 새 키 설정 96 µs: 2.25K key table 사용
이 package는 저자의 암호화 routine에서 가장 중요한 최적화를 구현했지만 일반적인 저수준 최적화가 다소 약해 39~106% 느렸습니다. 반면 빠른 `crypt(3)`와 password cracking을 목표로 같은 아이디어를 key 설정에 적용하여 인상적인 결과를 냈고 MIT DES library의 나머지도 구현했습니다.
출처: `eay@psych.psy.uq.oz.au`, `comp.sources.misc` 경유
덴마크의 빠른 crypt(3) package
120-130이 package의 DES routine은 `crypt` 함수 loop 안에 들어 있어 저자는 분리해 성능을 측정하지 않았습니다. 한 DES iteration에 SPARC instruction 26개를 사용합니다. 위 Quick(64K)은 21개, Small(2K)은 37개를 사용합니다.
저자는 상대 구현이 280K table을 사용한다고 주장했지만 iteration 계산은 128K만 사용하는 것으로 보였습니다. Table과 code는 machine 독립적입니다.
출처: `glad@daimi.aau.dk`, `alt.sources` 또는 `comp.sources.misc` 경유
스웨덴 Kerberos DES library 재구현
131-142- 암호화당 108 µs: 34K table 사용
- 새 키 설정 134 µs: 이 속도를 위해 32K key table 사용
사용한 table은 machine 독립적으로 보입니다. Machine architecture가 허용하면 `long` load 하나를 `char` load 네 개 대신 사용하는 등 특수 case code가 많이 포함된 것으로 보입니다.
출처: `chalmers.se:pub/des`
영국 crack 3.3c package
143-150앞의 `crypt`와 마찬가지로 DES routine이 loop 안에 들어 있고 `crypt` 용도로 크게 수정되어 있습니다. Iteration code는 16K table을 사용하며 느린 것으로 보입니다.
출처: `aem@aber.ac.uk`, `alt.sources` 또는 `comp.sources.misc` 경유
최적화된 Kerberos·Athena code
151-160이 구현은 byte order에 의존하는 이른바 `highly optimized` Kerberos·Athena code입니다.
- 암호화당 165 µs: 6K table 사용
- 새 키 설정 478 µs: 1K 미만의 key table 사용
Code의 설명과 달리 table을 machine 독립적으로 만들면서도 더 빠른 code와 더 작은 table을 얻을 수 있었습니다.
출처: `prep.ai.mit.edu`
UC Berkeley code
161-168이 구현은 machine endian 특성에 의존합니다.
- 암호화당 226 µs
- 새 키 설정 10,848 µs
Table 크기는 분명하지 않지만 작아 보이지 않습니다. 출처: `wuarchive.wustl.edu`.
동기와 역사
169-203동기와 역사
저자는 DES routine이 필요했지만 Sun manual page에 문서화된 routine은 존재하지 않거나 core dump를 냈다고 설명합니다. Kerberos가 DES를 사용한다는 말을 듣고 그 routine을 쓰려 했으나 code가 지나치게 복잡하고 IP, E, FP 같은 연산의 규칙적인 구조를 활용하지 않았으며 매우 느렸다고 평가했습니다.
또한 기존 구현은 data 이동을 줄이고 단순화하는 대신 L1, R1, L2, R2 등을 사용해 data 이동을 더 일관되게 보이게 하려고 statement를 늘렸고, 성능 향상 없이 code만 흐리는 machine별 tweak가 많았다고 비판합니다. 그래서 검증 program의 test data만 가져오고 나머지를 다시 작성했습니다.
나중에 앞서 언급한 `crypt(3)` package가 table lookup 한 번에 S-box 두 개를 계산하는 것을 보고 같은 방식을 채택했습니다. 상대 구현은 절반의 S-box indexing에 편한 형태와 나머지 절반에 편한 형태 두 가지로 working data를 유지했지만, 저자는 첫 절반에 맞는 형태 하나만 유지하고 간단한 rotate로 다른 절반을 얻었습니다.
그 결과 data 조작과 table 크기를 거의 절반으로 줄였습니다. 다만 상대 table이 `crypt(3)` 전용 정보를 encoding했을 가능성은 확인하지 않았습니다.
저자는 이 C version이 이식 가능하고 `ifdef`는 성능 개선에만 쓰이며, SPARC용 hand-written assembly version보다 빠르다는 점을 장점으로 듭니다.
Porting 참고 사항
204-232Porting 참고 사항
저자는 endian 특성과 다른 machine 특성에 의존하여 machine마다 다른 code와 lookup table을 만드는 거대한 구현을 피하려 했습니다. Kerberos의 endian별 최적화는 code를 흐리면서 더 단순한 machine 독립적 방식보다 느렸다고 평가합니다. 다만 이식성 고려는 필요하므로 register variable 수를 달리하는 option을 포함했습니다.
- 1. 모든 대상은 byte 단위 주소 지정이 가능하고 byte는 8-bit라고 가정합니다. Byte order에는 의존하지 않습니다. Word pointer와 char pointer를 자유롭게 cast할 수 있다고 가정하며 high bit가 설정될 수 있으면 항상 `unsigned char`를 사용합니다.
- 2. Typedef `word`는 32-bit unsigned integral type을 뜻합니다. `unsigned long`이 32-bit가 아니면 `desCore.h`의 typedef를 바꿔야 하며 모든 곳에서 `sizeof(word) == 4`를 가정합니다.
Key iteration 주변의 data load·store code에 endian별 최적화를 하지 않은 최악의 비용은 12% 미만입니다. 대신 input과 output 작업 영역을 word alignment에 맞출 필요가 없습니다.
선택적 성능 최적화
233-271선택적 성능 최적화
- 1. Machine capability와 가장 가까운 `i386`, `vax`, `mc68000`, `sparc` 중 하나를 정의하십시오. 정확한 효과는 `desCode.h` 시작 부분에 있습니다. 잘못 선택해도 DES code는 동작하며 이는 성능 tweak일 뿐입니다.
- 2. 기능하는 `asm` keyword가 있다면 ROR·ROL macro를 machine rotate instruction으로 바꾸십시오. 사용할 때마다 instruction 두 개와 temporary 하나, 즉 암호화·복호화당 약 32~40 instruction을 줄입니다.
GCC는 ROL/R macro를 machine rotate로 변환할 만큼 영리하다고 설명합니다.
이 최적화를 사용하면 assembly code와 비슷한 성능을 얻을 수 있지만 예외가 있습니다.
- 1. C에는 bit rotate operator가 없어 shift로 합성해야 합니다. Machine이 rotate를 지원하면 `asm` 접근이 빠르며 GCC 사용 시에는 필요하지 않습니다.
- 2. Machine에 32-bit register가 12개 미만이면 compiler가 좋은 code를 생성하기 어려울 수 있습니다.
`i386` 설정은 register variable을 세 개만 선언하여 386에 맞춥니다. GCC는 `ebx`, `esi`, `edi`를 사용할 수 있는 것으로 보입니다. 386의 32-bit register 일곱 개를 모두 쓰고 displacement가 있는 `scaled by 8` address mode 등을 활용하면 `DesQuickCore` routine을 각각 약 250 instruction으로 구현할 수 있습니다.
`DesSmall`에는 `des_keymap`을 재배열하여 S-box 번호를 index의 상위 부분, 6-bit data를 하위 부분에 두는 현재 배치를 서로 바꾸는 것이 도움이 됩니다.
저자는 편리하게 시험할 방법이 없어 386 전용 version을 제공하지 않았습니다. 이 desCore release에서 GCC는 모든 것을 register에 넣고 `DesQuickCore` routine당 약 370 instruction을 생성할 수 있었습니다.
Coding 참고 사항
272-313Coding 참고 사항
암호화·복호화 routine은 각각 필수 register variable 여섯 개를 사용하며 inner iteration 중 네 개를 동시에 사용합니다. 일부 설정에서는 constant 보관에 register를 최대 여덟 개 더 사용합니다.
저자는 constant 사용이 register 사용보다 비싸다고 가정합니다.
큰 constant를 register에 넣는 우선순위는 다음과 같습니다.
- 12-bit보다 큰 값: RISC와 CISC 모두에 불리함
- 127보다 큰 값: CISC에서 `movq` 또는 byte immediate를 사용할 수 없음
- 9~127: CISC shift immediate 또는 add/sub quick을 쓰지 못할 수 있음
- 1~8: 가장 저렴하므로 register에 넣지 않음
Compiler가 `table`과 `table+256`을 서로 다른 constant register에 할당해야 한다는 점을 알아채지 못하고 산술을 반복할 수 있으므로, 가능하고 유용할 때 이를 명시적인 `m` register variable에 할당합니다.
7-bit unsigned 이하 index에서는 indexing이 auto increment·decrement보다 저렴하거나 같다고 가정합니다. 68K와 VAX에서는 이 가정을 반대로 적용합니다.
Address는 register 두 개 또는 register 하나와 작은 constant로 저렴하게 만들 수 있다고 가정합니다. 68000에서는 `two registers and small offset` 형식을 제한적으로 사용합니다. 모든 index scaling은 명시적으로 수행하며 `log2(sizeof)`에 해당하는 숨은 shift는 없습니다.
단순한 compiler도 hidden temporary를 하나보다 많이 필요로 하지 않도록 code를 작성하여 모든 값이 register에 들어갈 가능성을 높였습니다. 다시 작성할 때 이 미묘한 점을 기억해야 합니다.
현재 temporary 두 개가 필요한 code fragment도 있지만 이를 고치면 macro 구조가 깨지거나 temporary를 하나 더 선언해야 합니다.
특수 고효율 data 형식
314-330특수 고효율 data 형식
대부분의 경우 bit는 S7 S5 S3 S1 순서를 위한 다음 배치로 조작됩니다.
`x` bit도 실제로 존재하며 S-box 위치를 강조한 표현입니다. S6 S4 S2 S0 계산 때는 4-bit left rotate를 적용합니다.
오른쪽 끝 두 bit는 보통 clear하여 하위 byte를 S-box mapping table index로 사용할 수 있게 합니다. 그다음 두 `x` bit에는 table의 다른 부분에 접근하기 위한 여러 값을 설정합니다.
Routine 사용법
331-389Routine 사용법
`DesData` type의 8-byte 영역 pointer는 DES key와 input·output block을 보관합니다.
`DesKeys` type의 128-byte 영역 pointer는 전체 768-bit key를 보관하며 long alignment가 필요합니다.
`DesQuickInit()`은 이름에 `Quick`이 들어간 다른 routine보다 먼저 호출해야 하며 필요한 특수 64K table을 생성합니다. `DesQuickDone()`은 이 table을 해제합니다.
`DesMethod(m, k)`에서 `m`은 128-byte block, `k`는 8-byte DES key를 가리킵니다. Key는 odd parity여야 하며 그렇지 않으면 -1을 반환합니다. Weak 또는 semi-weak key여서는 안 되며 그렇지 않으면 -2를 반환합니다. 정상적으로는 0을 반환합니다.
`m`은 `k`로 채워져 이후 routine이 `m`을 사용하면 key `k`에 의한 표준 DES 암호화·복호화처럼 동작합니다. `DesMethod()`를 쓰면 표준 56-bit key를 제공하지만 `m`을 직접 채우면 비표준 768-bit key를 얻습니다.
1024-bit가 아니라 768-bit인 이유는 각 byte의 최하위 두 bit를 사용하지 않기 때문입니다. 이 두 bit에는 일부 machine에서 암호화·복호화를 빠르게 하는 magic constant가 들어가며 각 byte는 특정 iteration의 특정 S-box를 제어합니다.
768-bit 형식을 직접 사용하지 않는 것이 좋습니다. 저자는 S-box mapping 순서 등으로 지정된 128개의 6-bit byte를 올바른 형식으로 바꾸는 routine이 필요하며, 여기에는 byte 결합과 rotate가 필요하다고 설명합니다.
`Des{Small|Quick}{Fips|Core}{Encrypt|Decrypt}(d, m, s)`는 `s`의 8-byte에 DES를 수행하여 `d`의 8-byte에 기록합니다. `d`와 `s`는 `char *`이고 `m`은 앞에서 설명한 768-bit key입니다.
`Encrypt|Decrypt`는 암호화 또는 복호화를 선택합니다. `Fips|Core`는 완전한 표준 FIPS initial·final permutation 수행 여부를 정합니다. 수행하지 않으면 data를 비표준 bit order, 즉 IP/FP 없는 FIPS 형식으로 load·store합니다.
Fips는 Quick을 10%, Small을 9% 느리게 합니다.
`Small|Quick`은 일반 routine과 추가 memory 64K를 쓰는 고속 routine 중 하나를 선택합니다. Small은 Quick보다 50% 느리지만 Quick은 memory를 32배 사용합니다. Quick은 encryption filter처럼 DES만 수행하는 program을 위한 것입니다.
Machine에서 compile하기
390-399Machine에서 compile하기
Porting 절에서 설명한 대로 code에는 `desTest.c`의 `now()` macro를 제외하면 machine dependency가 없습니다. 생성되는 모든 table은 machine 독립적입니다. Compiler에 맞는 최대 optimization flag로 Makefile을 수정해야 합니다.
Kerberos와 DES library 가속
400-409Kerberos와 DES library 가속
`desUtil.c`에는 `des_key_sched()`과 `des_ecb_encrypt()` 함수로 Kerberos 호환 interface가 포함되어 있습니다. Kerberos 또는 호환 code에서 사용하려면 linker command line에서 `desCore.a`를 Kerberos 호환 library보다 앞에 두십시오.
`desCore.h`를 include할 필요는 없고 Kerberos library가 제공하는 header만 include하면 됩니다.
다른 용도
410-414다른 용도
`desCode.h`의 macro는 더 복잡한 암호화 routine에 inline DES 함수를 넣는 데 유용합니다.
요약과 해설
descore-readme.rst:1-414이 문서는 현재 Crypto API 설계 문서라기보다 Linux source에 포함된 역사적 `descore.shar` README입니다. 1992년 당시 SPARC·68000·i386 환경에서 DES 성능과 table·register tradeoff를 기록합니다.
기술적으로는 byte-order 독립성, 32-bit `word` 가정, S-box 두 개를 한 lookup으로 처리하는 bit 배치, Small·Quick 및 Fips·Core variant, 768-bit 내부 key 형식이 핵심입니다. 시대적이고 주관적인 성능 평가는 원문의 관점임을 유지해 번역했으며 수치·함수명·source path를 보존했습니다.