Literaturverzeichnis

[BEUT] Beutelspacher, Albrecht: Kryptologie, 2. Auflage, Vieweg, 1991.

[BLUM] Blum, L, M. Blum, M. Shub: A Simple Unpredictable Pseudo-Random Number Generator, SIAM Journal on Computing, Vol. 15, No.2, 1986, S.364-383.

[Bos1] Bosch, Karl: Elementare Einfiihrung in die Wahrscheinlichkeitsrech­nung, Vieweg, 1984.

[Bos2] Bosch, Karl: Elementare Einfiihrung in die angewandte Statistik, Vieweg, 1984.

[Boss] Bosselaers, Antoon, Rene Govaerts, Joos Vandewalle: Comparison of three modular reduction functions, in: Advances in Cryptology, CRYPTO 93, Lecture Notes in Computer Science 773, S. 175-186, Springer, 1994.

[BRES] Bressoud, David M.: Factorization and Primality Testing, Springer, 1989

[BUND] Bundschuh, Peter: Einfiihrung in die Zahlentheorie, 3. Auflage, Springer, 1996.

[COHE] Cohen, Henri: A Course in Computational Algebraic Number Theory, Springer, 1993.

[DEIT] Deitel, H. M., P. J. Deitel: C++ How To Program, Prentice Hall, 1994.

[DENE] Denert, Ernst: Software-Engineering, Springer, 1991.

[DIFF] Diffie, Whitfield, Martin E. Hellman: New Directions in Cryptography, IEEE Trans. Information Theory, S. 644-654, Vol. IT-22, 1976.

[DoBP] Dobbertin, Hans, Antoon Bosselaers, Bart Preneel: RIPEMD-160, a strengthened version of RIPEMD, in D. Gollman (Hrsg.): Fast Software Encryption, Third International Workshop, Lecture Notes on Computer Science 1039, S. 71-82, Springer, 1996.

[DuKA] Dusse, Stephen R., Burton. S. Kaliski: A Cryptographic Library for the Motorola DSP56000, in: Advances in Cryptology, EUROCRYPT 90, Lecture Notes in Computer Science No. 473, S. 230-244, Springer, New York, 1990.

[DUNC] Duncan, Ray: Advanced OS/2-Programming: The Microsoft Guide to the OS/2-kernel for assembly language and C programmers, Microsoft Press, Redmond, Washington, 1981.

[ELST] Ellis, Margaret A., Bjame Stroustrup: The Annotated C++ Reference Manual, Addison-Wesley, Reading, MA, 1990.

302 Literaturverzeichnis

[ENOL] Endl, Kurth, Wolfgang Luh: Analysis I, Akademische Vedagsgesellschaft Wiesbaden, 1977.

[EVAN] Evans, David: LCLint Users Guide, MIT Laboratory for Computer Science.

[EAST] Eastlake, D., S. Crocker, J. Schiller: Randomness Recommendations for Security, RFC1750, 1994.

[FIAT] Fiat, Amos, Adi Shamir: How to prove yourself: Practical Solutions to Identification and Signature Problems, in: Advances in Cryptology, CRYPTO 86, Lecture Notes in Computer Science 263, S. 186-194, Springer, New York, 1987.

[FIPS] Federal Information Processing Standard Publication 140 - 1: Security requirements for cryptographic modules, US Department of Com­mercelNational Institute of Standards and Technology (NIST), 1992.

[FIsc] Fischer, Gerd, Reinhard Sacher: Einfuhrung in die Algebra, Teubner, 1974.

[fuMY] Fumy, Walter, Hans Peter RieB: Kryptographie, 2. Aufl., Oldenbourg, 1994.

[GIMP] Gimpel Software: PC-lint, A Diagnostic Facility for C and C++.

[GLAD] Glade, Albert, Helmut Reimer, Bruno Struif (Hrsg.): Digitale Signatur & Sicherheitssensitive Anwendungen, DuD-Fachbeitrage, Vieweg, 1995.

[GORO] Gordon, J. A.: Strong Primes are Easy to Find, Advances in Cryptology, Proceedings of Eurocrypt 84, S. 216-223, Springer, 1985.

[HALM] Halmos, Paul, R.: Naive Mengenlehre, 3. Auflage, Vandenhoeck & Ruprecht, G6ttingen, 1972.

[HARB] Harbison, Samuel P, Guy L. Steele jr.: C, a reference manual, 4th ed., Prentice Hall, Englewood Cliffs, 1995.

[HATI] Hatton, Les: Safer C: Developing Software for High-integrity and Safety­critical Systems, McGraw-Hill, London, 1995.

[HElD] Heider, Franz-Peter: Quadratische Kongruenzen, unverOffentlichtes Ma­nuskript, K61n, 1997.

[HKW] Heider, Franz-Peter, Detlef Kraus, Michael Welschenbach: Mathemati­sche Methoden der Kryptoanalyse, DuD-Fachbeitrage, Vieweg, Braun­schweig, 1985.

[HEQU] Heise, Werner, Pasquale Quattrocchi: Informations- und Codierung­stheorie, Springer, 1983.

[IS01] ISO/IEC 10118-3: Information Technology - Security Techniques -Hash-functions-Part 3: Dedicated hash-functions, CD, 1996.

Literaturverzeichnis 303

[KNUT] Knuth, Donald Ervin: The Art of Computer Programming, Vol. 2: Semi­numerical Algorithms, 2nd Edition, Addison-Wesley, Reading, MA, 1981.

[KOBL] Koblitz, Neal: A course in number theory and cryptography, Springer, 2nd ed. 1994.

[KRAN] Kranakis, Evangelos: Primality and Cryptography, Wiley-Teubner Series in Computer Science, 1986.

[LIND] van der Linden, Peter: Expert C Programming, SunSoftlPrentice Hall, Mountain View, CA, 1994.

[LIPp] Lippman, Stanley, B.: C++ Primer, 2nd Edition, Addison-Wesley, Reading, MA, 1993.

[MAGU] Maguire, Stephen A.: Writing Solid Code, Microsoft Press, Redmond, Washington, 1993.

[MATI] Matthews, Tim: Suggestions for Random Number Generation in Soft­ware, RSA Data Security Engineering Report, December 1995.

[MENE] Menezes, Alfred J.: Elliptic Curve Public Key Cryptosystems, Kluwer Academic Publishers, 1993.

[MOV] Menezes, Alfred J., Paul van Oorschot, Scott A. Vanstone, Handbook of Applied Cryptography, CRC Press, 1997.

[MONT] Montgomery, Peter L.: Modular Multiplication without Trial Division, Mathematics of Computation, S. 519-521,44 (170),1985.

[MURP] Murphy, Mark L.: C/C++ Software Quality Tools, Prentice Hall, New Jersey, 1996.

[NIED] Niederreiter, Harald: Random Number Generation and Quasi-Monte Carlo Methods, SIAM, Philadelphia, 1992.

[NIVE] Niven, Ivan, Herbert S. Zuckerman: Einfuhrung in die Zahlentheorie Bd. I und II, Bibliographisches Institut, Mannheim, 1972.

[PLA1] Plauger, P. J.: The Standard C Library, Prentice-Hall, Englewood Cliffs, New Jersey, 1992.

[PLA2] Plauger, P. J.: The Draft Standard C++ Library, Prentice-Hall, Engle­wood Cliffs, New Jersey, 1995.

[PETZ] Petzold, Charles: Programming Windows: The Microsoft Guide to Writ­ing Applications for Windows 3.1, Microsoft Press, Redmond, Washig­ton, 1992.

[PREN] Preneel, Bart: Analysis and design of cryptographic hash functions, Doktorarbeit an der Katholieke Universiteit Leuven, 1993.

304 Literaturverzeichnis

[REIN] Reinhold, Arnold: P= ?NP Doesn't Affect Cryptography, http://world.std.coml-reinholdlp=np.txt.Mai1996.

[RIEs] Riesel, Hans: Prime Numbers and Computer Methods Jor Factorization, Birkhauser, Boston, 1994.

[RIvE] Rivest, Ronald, Adi Shamir, Leonard Adleman: A Method Jor Obtaining Digital Signatures, Communications of the ACM 21, S. 120-126, 1978.

[ROSE] Rose, H: E.: A course in number theory, 2nd edition, Oxford University Press, Oxford, 1994.

[SAGA] Sagan, Carl: Cosmos, Random House, New York, 1980.

[SALO] Salomaa, Arto: Public-Key Cryptography, Second Edition, Springer, 1996.

[SCHN] Schneier, Bruce: Applied Cryptography, Second Edition, John Wiley & sons, New York, 1996.

[SCHO] Schonhage, Arnold: A Lower Bound on the Length oj Addition Chains, Theoretical Computer Science, S. 229-242, Vol. 1, 1975.

[SKAL] Skaller, John Maxwell: Multiple Precision Arithmetic in C, in: Schumacher, Dale (Editor): Software Solutions in C, Academic Press, S. 343-454, 1994.

[SPUL] Spuler, David A.: C++ and C Debugging, Testing and Reliability, Prentice Hall, New Jersey, 1994.

[STAL] Stallman, Richard M.: Using and Porting GNU CC, Free Software Foun­dation.

[STIN] Stinson, Douglas R.: Cryptography - Theory and Pratice, Prentice Hall, New Jersey, 1995.

[STR1] Stroustrup, Bjarne: The C++ Programming Language, 3rd Edition, Addison-Wesley, Reading, MA, 1997.

[STR2] Stroustrup, Bjarne: The Design and Evolution oj C++, Addison-Wesley, Reading, MA, 1994.

[TEAL] Teale, Steve: C++ IOStreams Handbook, Addison-Wesley, Reading, MA,1993.

[YACO] Y. Yacobi, Exponentiating Jaster with Addition Chains, in: Advances in Cryptology, EUROCRYPT 90, Lecture Notes in Computer Science 473, S. 222-229, Springer, New York, 1990.

Anhang A: Verzeichnis der C-Funktionen

In diesem Anhang werden die C-Funktionen des ersten Teils mit ihren Signatu­ren aufgelistet. Die Operatoren und Funktionen der C++-Klasse LINT sind bereits in auf den Seiten 230-230 und 239-248 iibersichtlich zusammengestellt.

Eingabe/Ausgabe, Zuweisung, Konvertierung, Vergleiche

void cpy_l

void fswap_l

int equ_l

void

Funktion

(CLINT dest_l,

CLINT src_l) ;

(CLINT a_I,

CLINT b_l) ;

(CLINT a_I,

CLINT b_l) ;

(CLINT a_I,

CLINT b_l);

u2clint_l (CLINT nurn_l,

USHORT ul);

void u12clint_l (CLINT nurn_l,

ULONG ul);

char * clint2str_l (CLINT n_l,

USHORT b);

int

str2clint_l (CLINT n_l, char *N,

USHORT b);

unsigned int

vcheck_l (CLINT n_l) ;

ErHiuterung

Zuweisung von src_l an dest_l

Test auf Gleichheit von a_I und b_l

GroBenvergleich von a_I und b_l

Konvertierung USHORT nach CLINT

Konvertierung ULONG nach CLINT

Konvertierung von CLINT in eine Zei­

chenkette zur Basis b

Konvertierung einer Zeichenkette zur Ba­

sis b nach CLINT

CLINT-Formatpriifung

306 Anhang A: Verzeichnis der C-Funktionen

Grundrechenarten

Funktion

(CLINT a_I, CLINT b_l,

CLINT Eel)

(CLINT a_I, USHORT b,

CLINT 8_1)

(CLINT a_I, CLINT b_l,

CLINT 8_1)

(CLINT a_I, USHORT b, CLINT c_l)

(CLINT a_I, CLINT b_l, CLINT p_l)

(CLINT a_I, USHORT b,

CLINT p_l)

(CLINT a_I, CLINT b_l,

CLINT ~1, CLINT r_l)

(CLINT a_I, USHORT b,

CLINT ~1, CLINT r_l)

Erlauterung

Addition: Summe von a_I und b_l,

Ausgabe in 8_1

Gemischte Addition: Summe von a_I

und b, Ausgabe in 8_1

Inkrementierung von a_I

Subtraktion: Differenz von a_I und b_l, Ausgabe in 8_1

Gemischte Subtraktion: Differenz von

a_I und b, Ausgabe in 8_1

Dekrementierung von a_I

Multiplikation: Produkt von a_I und

b_l, Ausgabe in p_l

Gemischte Multiplikation: Produkt von

a_I und b, Ausgabe in p_l

Quadrierung von a_I, Ausgabe in p_l

Division mit Rest: Division von a_I

durch b_l, Quotient in ~1, Rest in r_l

Gemischte Division mit Rest: Division

von a_I durch b, Quotient in ~1, Rest

inr_l

Anhang A: Verzeichnis der C-Funktionen 30'7

Modulare Arithmetik

Funktion

int mod_l (CLINT d_l. CLINT n_l,

CLINT r_l) ;

USHORT wnod_l (CLINT d_l, USHORT n);

int mod2 - 1 (CLINT d_l, ULONG k,

CLINT r_l) ;

int mequ_l (CLINT a_I, CLINT b_l.

CLINT m_l) ;

int madd_l (CLINT a_I, CLINT b_l,

CLINT c_l, CLINT m_l) ;

int umadd_l (CLINT a_I, USHORT b,

CLINT c_l, CLINT m_I);

int msub_l (CLINT a_I, CLINT b_l,

CLINT c_l, CLINT m_l) ;

int wnsub_l (CLINT a_I, USHORT b,

CLINT c_l, CLINT m_I);

int l1Dl\ul - 1 (CLINT a_I, CLINT b_l,

CLINT c_l, CLINT m_l) ;

void mulmon_l (CLINT a_I, CLINT b_l,

CLINT n_l, USHORT nprime, USHORT Iogr, CLINT p_l) ;

int ununul - 1 (CLINT a_I, USHORT b,

CLINT c_l, CLINT m_I);

int msqr_l (CLINT a_I, CLINT c_l,

CLINT m_l) ;

ErHiuterung

Restbildung von d_1 mod n_l, Ausgabe inr_ I

Restbildung d_1 mod n

Restbildung d_1 mod 2k

Test auf Gleichheit vonn a_I und b_1 modm_1

Modulare Addition: Addition von a_I und b_1 mod m_l, Ausgabe in c_1

Gemischte modulare Addition: Addition von a_I und b mod m_l, Ausgabe in c_1

Modulare Subtraktion: Subtraktion von a_I und b_1 mod m_l, Ausgabe in c_1

Gemischte modulare Subtraktion: Sub-traktion von a_I und b mod m_l, Ausga-be in c_1

Modulare Multiplikation: Multiplikation von a_I und b_1 mod m_l, Ausgabe in c_ I

Modulare Multiplikation von a_I und b_1 mod n_l, Produkt in p_1 (Montgomery-Methode)

Gemischte modulare Multiplikation von a_I und b_1 mod n_l, Produkt in p_1

Modulare Quadrierung von a_I mod n_l, Quadrat in p_1

308 Anhang A: Verzeichnis der C-Funktionen

Modulare Arithmetik

int

Funktion

(CLINT bas_l, CLINT exp_l, CLINT rest_l, CLINT m_l);

(CLINT bas_l, CLINT exp_l, CLINT rest_l, CLINT m_l);

mexpSm_l (CLINT bas_l, CLINT exp_l, CLINT rest_l, CLINT m_l);

int maxpkm_l (CLINT bas_l, CLINT exp_l,

CLINT rest_l, CLINT m_l);

int umaxp_l (CLINT bas_l, USHORT e,

CLINT rest_l, CLINT m_l);

int

(USHORT bas, CLINT e_l, CLINT rest_l, CLINT m_l) ;

wmaxpm_l (USHORT bas, CLINT e_l, CLINT rest_l, CLINT m_l) ;

(CLINT a_l, USHORT k, CLINT p_l, CLINT m_l) ;

ErHiuterung

Modulare Potenzierung,

25-are Methode

Modulare Potenzierung,

2k-are Methode, dynamo Speicher

Montgomery-Potenzierung, 25-are Me­thode, ungerader Modulus

Montgomery-Potenzierung, 25-are Me­thode, ungerader Modulus

Modulare Potenzierung, USHORT­Exponent

Modulare Potenzierung, USHORT-Basis

Montgomery-Potenzierung, USHORT­Basis, Modulus ungerade

Modulare Potenzierung, Zweierpotenz­Exponent k

Anhang A: Verzeichnis der C-Funktionen 309

Bitweise Operationen

Funktion

int

setbit - 1 (CLINT a_I,

unsigned int pos)

int

testbit - 1 (CLINT a_I,

unsigned int pos)

int

clearbit_l (CLINT a_I,

int

unsigned int pos)

(CLINT a_I, CLINT b_l,

CLINT c_l)

(CLINT a_I, CLINT b_l,

CLINT c_l)

(CLINT a_I, CLINT b_l,

CLINT c_l)

shift_l (CLINT a_I,

long int noofbits)

ErHiuterung

Testen und Setzen des Bit in Position pos

von a_I

Testen des Bit in Position pos von a_I

Testen und Loschen des Bit in Position

pos von a_I

Bitweises UND von a_I und b_l, Aus­

gabein c_l

Bitweises ODER von a_I und b_l, Aus­

gabe in c_l

Bitweises exklusives ODER (XOR) von

a_I und b_l, Ausgabe in c_l

Linksschieben von a_I urn I Bit

Rechtsschieben von a_I urn I Bit

LinkslRechtsschieben von a_I urn die

Anzahl von noofbits Bit

310 Anhang A: Verzeichnis der C-Funktionen

Zahlentheoretische Funktionen

Funktion

unsigned iroot_l (CLINT a_l, CLINT b_l)

unsigned ld_l (CLINT a_l)

void gg'l'_l (CLINT a_l, CLINT b_l,

CLINT g_l)

void xgg'l'_l (CLINT a_l, CLINT b_l,

CLINT g_l, CLINT u_l, int *sign_u, CLINT v_l, int *sign_v)

void inv_l (CLINT a_l, CLINT n_l,

CLINT g_l, CLINT i_l)

void kgV_l (CLINT a_l, CLINT b_l,

CLINT v_l)

int chinrest_l (unsigned noofeq,

clint** koeff_l, CLINT x_l)

int jacobi_l (CLINT a_l, CLINT b_l)

int proot_l (CLINT a_l, CLINT p_l,

CLINT x_l)

int

(CLINT a_l, CLINT p_l, CLINT ~l, CLINT x_l)

primwurz_l (CLINT x_l, unsigned noofprimes, clint** primes_l)

USHORT sieve_l (CLINT a_l,

unsigned noofsmallprimes)

int prime_l (CLINT n_l,

unsigned noofsmallprimes, unsigned iterations)

Erliiuterung

Ganzzahliger Anteil der Quadratwurzel von a_l, Ausgabe in b_l

Anzahl der Biniirstellen von a_l

GroBter gemeinsamer Teiler von a_l und b_l, Ausgabe in g_l

GroBter gemeinsamer Teiler von a_l und b_l und Darstellung des ggT in u_l und v_l mit Vorzeichen in sign_u und sign_v

ggT von a_l mod n_l und Inverses von a_l modn_l

Kleinstes gemeinsames Vielfaches von a_l und b_l, Ausgabe in v_l

Losung simultaner linearer Kongruenzen, Ausgabe in x_l

Legendre-/Jacobi-Symbol von a_l tiber b_l

Quadratwurzel von a_l mod p_l, Aus­gabe in x_l

Quadratwurzel von a_l mod p_l·~l, Ausgabe in x_l

Bestimmung einer Primitivwurzel modulo n, Ausgabe in x_l

Divisionssieb, Division von a_l durch kleine Primzahlen

Miller-Rabin-Primzahltest von n_l mit Divisionssieb

Anhang A: Verzeichnis der C-Funktionen 311

Erzeugung von PseudozuJallszahlen

Funktion

clint * rand64_1 (void)

void

rand_l (CLINT r_l, int 1)

UCHAR

ucrand64_1 (void)

USHORT

usrand64 1 (void)

ULONG

ulrand64 1 (void)

clint *

clint * ulseed64 1 (ULONG seed)

int

randbit 1 (void)

clint * randBBS 1 (void)

UCHAR

ucrandBBS 1 (void)

USHORT

usrandBBS 1 (void)

ULONG

ulrandBBS 1 (void)

void

seedBBS 1 (CLINT seed_I)

void

ulseedBBS 1 (ULONG seed)

ErHiuterung

64-Bit Zufallszahlengenerator

CLINT-Zufallszahlen mit 1 Binarstellen,

Iineare Kongruenzen

Generator fijr Zufallszahlen vom Typ

UCHAR

Generator fijr Zufallszahlen vom Typ

USHORT

Generator fijr Zufallszahlen vom Typ

ULONG

Initialisierung von rand64_1 ()

mit CLINT-Wert

Initialisierung von rand64_1 ( )

mit ULONG-Wert

BBS-Bitgenerator

CLINT-Zufallszahlen mit 1 Binarstellen,

BBS-Bitgenerator

BBS-Generator ftir Zufallszahlen vom

TypUCHAR

BBS-Generator fijr Zufallszahlen vom

TypUSHORT

BBS-Generator fijr Zufallszahlen vom

TypULONG

Initialisierung von randbi t_l ( )

mit CLINT-Wert

Initialisierung von randbi t_l () mit

ULONG-Wert

312 Anhang A: Verzeichnis der C-Funktionen

Register-Verwaltung

Funktion Erlauterung

void Setzen der Registerzahl set_Doofregs_l (unsigned int nregs)

int Erzeugen der CLINT-Registerbank

create_reg_l (void)

clint * get_reg_l (unsigned int reg)

int purge_reg_l (unsigned int reg)

int purgeall_reg_l (void)

void free_reg_l (void)

clint * create_l (void)

void purge_l (CLINT n_l)

void

free_l (CLINT n_l);

Erzeugen einer Referenz auf Register reg

der Registerbank

Loschen eines Registers der Registerbank

durch Uberschreiben

Loschen aller Registers der Registerbank

durch Uberschreiben

Loschen aller Registers der Registerbank

durch Uberschreiben und Riickgabe des

Speichers

Erzeugen eines CLINT-Registers

Loschen eines CLINT-Objekts durch

Uberschreiben

Loschen eines Registers durch Uber­

schreiben und Riickgabe des Speichers

Anhang B: Die Makros

Makrobezeichner

E_DBZ

E_OFL

E_UFL

E_MAL

E_NOR

E_BOR

E_MOD

E_VCHECK_OFL

E_VCHECK_LDZ

E_VCHECK_MEM

Fehlercodes und Statuswerte

Definition Beschreibung

-I

-2

-3

--4

-5

-6

-7

2

-I

Division durch Null

Uberlauf

Unterlauf

Fehler bei Memory Allocation

Register nicht vorhanden

Ungiiltige Basis in str2clint_l ()

Gerader Modulus bei Montgomery-Reduzierung

vcheck_l () -Warnung: Zahl zu lang

vcheck_l () -Warnung: Fiihrende Nullen

vcheck_l ( ) -Fehler: Null-Pointer

314 Anhang B: Die Makros

Weitere Konstanten

Makrobezeichner Defmition Beschreibung

BASE Ox10000 Basis B = 216 des CLINT-Zahlformats

BASEMJ:NONE OxffffU B-1 als USHORT-Typ

BASEMJ:NONEL OxffffUL B-1 als ULONG-Typ

DBASEMJ:NONE OxffffffffUL B2 - 1 als ULONG-Typ

BASEDJ:V2 Ox8000U LBI2J

NOOFREGS 16U Standard-Anzahl der Register in

Registerbank

BJ:TPERDGT 16UL Anzahl der Binlirstellen pro CLINT-

Stelle

LDBJ:TPERDGT 4U Logarithmus von BITPERDGT

CLJ:NTMAXDJ:GJ:T 256U Maximale Anzahl der Stellen zur

Basis B eines CLINT-Objekts

CLJ:NTMAXSHORT (CLINTMAXDIGIT + 1) Anzahl der fur ein CLINT-Objekt zu

allokierenden USHORTs

CLJ:NTMAXBYTE (CLINTMAXSHORT « 1) Anzahl der fUr ein CLINT-Objekt

allokierten Bytes

CLJ:NTMAXBJ:T (CLINTMAXDIGIT « 4) Maximale Anzahl der Binlirstellen

eines CLINT-Objekts

Anhang B: Die Makros

Syntax

assign_l

(a_l, b_l)

Makros mit Parametern

Definition

printf("%s%s\n%u bit\n\n",\

(S) ,hexstr_l(A) , ld_l(A))

clint2str_l((n) ,10)

(a_l) [0) = (MIN( (a_l) [0), \

(USHORT)CLINTMAXDIGIT)) ;\

rmldzrs_l ( (a_l) )

315

Beschreibung

Standard-Ausgabe eines

CLINT-Objekts

Konvertierung eines

CLINT-Objekts in

Hex-Darstellung

Konvertierung eines

CLINT-Objekts in

Dezimal-Darstellung

Konvertierung eines

CLINT-Objekts in

Oktal-Darstellung

Konvertierung eines

CLINT-Objekts in

Binar-Darstellung

Zuweisung

a_l ~ ULONG ul

Zuweisung

a 1 ~ b_l

Reduktion modulo Nmax+l

Lese-/Schreibzugriff auf

die Stellenzahl von n_1

zur Basis B

Zeiger auf

niedrigstwertige Stelle

eines CLINT-Objekts

Zeiger auf hiichstwertige

Stelle eines CLINT­

Objekts

316

Syntax

swap (a,b)

Makros mit Parametern

Definition

(whiIe«(n_l) [0) > 0) && \ «n_l) [(n_l) [0)) == 0» \

-- (n_l) [0)

Anhang B: Die Makros

Beschreibung

Entfernung fiihrender

Nullen von CLINT­

Objekt

«a) A= (b), (b) A= (a) ,\ Vertauschung

(a) A= (b»

(xor_1 ( (a_I) , (b_l) , (a_I) ) ,\ Vertauschung zweier

xor_1 «b_l) , (a_I) , (b_I», \ CLINT-Werte

xor_1 «a_I) , (b_l) , (a_I»)

1)

1)

1)

«*(a_l) == 1) && \ (*(lsdptr_1 (a_I» == 1»

Vergleich

a_I <b_1

Vergleich

a_I :5b_1

Vergleich a_I> b_1

Vergleich

a_I ~b_1

Vergleich

a_I> 0

Vergleich

a_I == 0

Vergleich

a_I == I

(It_1 «a_I) , (b_I»? (a_I): \ Minimum zweier

(b_l) ) CLINT-Werte

(gt_1 «a_I) , (b_I»? (a_I) : \ Maximum zweier

(b_l) ) CLINT-Werte

( * (a_I) == 0 I I (*(a_l) > 0 &&

\

\ (*(lsdptr_1 (a_I»\

& lU) == 0»

Test, ob a_I gerade ist

Anhang B: Die Makros

Syntax

mexp_l (a,e,p,n)

mexp_l (a,e,p,n)

initrand64_1t()

initrandBBS_lt()

Makros mit Parametern

Definition

\ (*(lsdptr_l (a_l))\

& IV) == 1)

mexpk_l ((a) , (e) , (p) , (n) )

mexp5_1 ((a) , (e) , (p) , (n) )

seed64_1((unsigned long) \

time (NULL) )

seedBBS_l( (unsigned long) \

time (NULL) )

prime_l((n) ,302,5)

317

Beschreibung

Test, ob a_l ungerade

ist

Potenzierung

Potenzierung, alternativ

Initialisierung des Zufallszahlengenerators rand64_1 () mit der

Systemzeit

Initialisierung des Bitgenerators randbi t_l () mit der

Systemzeit

Primzahltest mit fixen Parametern

Anbang C: Recbenzeiten

Die folgenden beiden Tabellen geben Rechenzeiten fUr einige Arithmetikfunktio­nen an, die mit einem Pentium-Prozessor mit 166 MHz Taktfrequenz und 32 Mbyte Hauptspeicher unter Windows 95 ermittelt wurden. Die Zeiten fUr jeweils n Operationen wurden gemessen und durch die Anzahl n dividiert; n betragt je nach Funktion zwischen 100 und 100.000.

Biniirstellen der Argumente, Angaben der Rechenzeiten in s

Funktionen

ohne 80x86- 128 256 512 768 1024 2048 Assembler-

Unterstiitzung

add_l 1,0.10--5 1,0.10--5 1,0.10--5 1,5.10-5 1,5.10-5 3,0.10-5

mul - 1 1,0.10--5 4,0.10-5 1,3·10-4 3,0·10-4 5,1·10-4 2,0.10-3

sqr_l 1,0.10-5 3,0.10-5 8,0.10-5 1,7·10-4 2,7·10-4 1,0.10-3

div_l 1,0.10--5 3,0.10--5 7,0.10-5 1,1·10-4 2,2·10-4 7,9·10-4

mmul - 1 4,0.10-5 1,0·10-4 3,5·10-4 7,5·10-4 1,3.10-3 5,0.10-3

msqr_l 3,0.10-5 1,0·10-4 2,9·10-4 6,2·10-4 1,0.10-3 4,0.10-3

mexpk_l 5,5.10-3 2,9.10-2 1,9.10-1 5,9.10-1 1,3 9,9

mexpkm_l 3,3.10-3 2,0.10-2 1,4.10-1 4,4.10-1 1,0 7,7

Deutlich ist zu erkennen, welche Einsparungen sich durch Verwendung der Qua­drierung gegeniiber der Multiplikation erzielen lassen. Ebenso Hillt sich die Uber­legenheit der in mexpkm_l () realisierten Montgomery-Pottmzierung erkennen, die etwa das 0,7-fache der Potenzierung mittels mexpk_l () benOtigt.

320 Anhang C: Rechenzeiten

Biniirstellen der Argumente, Angaben der Rechenzeiten in s

Funktionen

mit 80x86- 128 256 512 768 1024 2048 Assembler-

Unterstutzung

rnul - 1 1,0.10-5 2,0.10-5 6,0.10-5 1,2·10-4 2,1·10-4 8,1·10-4

sqr_l 1,0.10-5 1,0.10-5 4,0.10-5 6,0.10-5 1,0·10-4 3,7·10-4

* 5,0·10-6 2,0.10-5 2,5.10-5 5,0.10-5 9,0.10-5 2,7·10-4 div_l

rnrnul - 1 1,5.10-5 5,0.10-5 1,3·10-4 3,0·10-4 4,8·10-4 1,8.10-3

rnsqr_l 1,0.10-5 4,0.10-5 1,0·10-4 2,3·10-4 3,7·10-4 1,3.10-3

rnexpk_l 2,2.10-3 1,3.10-2 7,0.10-2 2,1.10-1 4,7.10-1 3,4

rnexpkrn_l 2,7.10-3 1,6.10-2 1,0.10-1 3,4.10-1 7,8.10-1 5,8

* Fur die Funktion di v_I () beziehen sich die Stellenzahlen auf die Dividenden, wiihrend die Di-

visoren jeweils halb so viele Stellen haben.

Die zweite Tabelle weist den zeitlichen Unterschied nach, der sich aus der Ein­beziehung der Assembler-Routinen ergibt. Durchgangig ist festzustellen, daB aus der Assernbler-Unterstiitzung ein Geschwindigkeitsvorteil urn den Faktor 2,5 re­sultiert. In absoluten Zahlen beeindruckt die Zeitdifferenz von 6,5 Sekunden fUr die Potenzierung mit Argurnenten der Lange 2048 Bit. Desweiteren ist zu berner­ken, daB der Abstand zwischen Multiplikation und Quadrierung noch etwas deut­licher ausfallt. Da die Funktionen rnulrnon_l () und sqrrnon_l () nicht als Assernbler-Routinen vorliegen, fallt die Montgomery-Potenzierung rnexprn_l ( ) in diesern Vergleich deutlich hinter rnexpk_l () zurUck. Hier besteht ein interes­santes Potential fUr weitere Verbesserung der Perforrnanz (vgl. Kap. 18).

Anhang D: Notationen

N Die Menge der natiirliehen Zahlen (einsehlieBlieh der Null)

N+ Die Menge der positiven nattirliehen Zahlen

Z Die Menge der ganzen Zahlen

ZII Restklassenring modulo n tiber den ganzen Zahlen

a Restklasse a + nZ, Element eines Restklassenringes modulo n

alb a teilt b ohne Rest

a == b mod n Kongruenz: a == b mod n:¢:::> n I (a - b)

a f- b Zuweisung von b an a

lal Betrag von a

ggT GroBter gemeinsamer Teiler

kg V Kleinstes gemeinsames Vielfaehes

€P( ) Euler'sehe Phi-Funktion

O() GroB-O (Landau'sehes O-Symbol): Ftir zwei reellwertige Funktio­nen/und g mit g(x) ~ 0 sehreibt man/= O(g) und sagt ,fist GroB­o von g", wenn es eine Konstante C gibt, so daB fix) ::; C·g(x) fUr alle hinreichend groBe Argumente x ist.

LxJ GroBte ganze Zahl unterhalb von x

r x 1 Kleinste ganze Zahl oberhalb von x

P Menge der in Polynomzeit 16sbaren Probleme

NP Menge der nieht in Polynomzeit losbaren Probleme

B B = 216, die Basis der Zahldarstellung ftir Objekte vom Typ CLINT

MAX8 Maximale Stellenzahl eines CLINT-Objektes zur Basis B

MAXb Maximale Stellenzahl eines CLINT-Objektes zur Basis 2

Nmax GroBte nattirliche Zahl, die dureh ein CLINT-Objekt darstellbar ist

Index

A

Abgeschlossenheit 55

einer Gruppe 142

add 58

add_I 17; 58

Addition 13; 16; 20

modulare 57

von Restklassen 54; 55

Additionsketten 82

Algorithmus

Addition 16

Binare Potenzierung modulo m 66

Binarer Euklidischer 136

Division mit Rest 41

Erweiterter Euklidischer 143; 145

Euklidischer 135

Fenster-Methode zur Potenzierung 86

Ganzzahliger Anteil der Quadratwuzel

149

Inverses modulo 2n 92

Jacobi-Symbol 155

Legendre-Symbol 153

U:isung 1inearer Kongruenzen 167; 169

M-are Potenzierung modulo m 70; 72

Multiplikation 27

Periodenlangen von Folgen 194

Primitivwurzeln modulo m 96

Quadratwurzel modulo p 161

Quadrierung 34; 35

Schliisselerzeugung nach Fiat-Shamir

172

Sieb des Eratosthenes 177

Subtraktion 20

Alphabet 57

and_l 106

Anordnung

von Stellen einer Zahl 11

A.quivalenzrelation 53

Assembler 297

Assoziativgesetz 5; 55

Ausgabe

einer Funktion 13

Authentisierung 277

B

big-end ian 260

Binomialverteilung 195

Binomische Formel 213

Brent-Alorithmus 194

c Caesar, Gaius Julius (100-44 v. Chr.) 57

Carmichael, Robert Daniel (1879-1967)

Carmichael-Zahlen 180

catch-Block 269

Certification Authority 284

Ch?-Test 195

Chinesischer Restsatz 164; 167; 169; 287

chinresU 170

clearbiU III CLINT II clint2str_1 120

cmp_1 112

cpy-I 117

create_I 130

create_reg_1 127

324

D

Dateien

Schreiben von LINT-Objekten 260

dec_I 24

Dekrement 24

Diffie-Hellman

Schliisselaustausch 96

digits_I II; 14; 18

Distributivgesetz 5; 55

div_1 41

Division

kurze 48

mit Rest 38; 53; 58; 99; 102

E

Einselement 55

Einweg-Funktion 283

Electronic Commerce 277

Element

inverses 55

neutrales 55

equ_1 114

Eratosthenes (276-195 v. Chr.) 3

Sieb des Eratosthenes 176

Euklid (ca. 300 v. Chr.) 3; 174

Erweiterter Euklidischer Algorithmus

143

Euklidischer Algorithmus 92; 135; 136

Euler, Leonhard (1707-1783) 3

Euler'sche Phi-Funktion 142; 277

Euler'sches Kriterium 152; 181

Euler-Pseudoprimzahlen 181

Satz von 142

Exceptions 269

F

Faktorisierung 164; 176; 279; 280

Fehlerbehandlung 268

Fermat, Pierre de (1601-1665) 3

Fermat-Test 180

Kleiner Satz von 142; 180

Fiat, Amos 172

free 212

free_I 132

free_reg_1 130

friend-Funktionen 237

fstream 260; 262

fswap_1 118

Funktion

gemischte 22

Funktionskopf 13

G

Garner-Algorithmus 167

Index

GauS, Carl Friedrich (1777-1855) 3; 53;

153

gcc 7;206;292

genprimes 177

Gesetz zur digita1en Signatur 277

geCreg_1 128

ggLI 136

GNU 7; 206

Gruppe 55

Gruppengesetze 56

H

Halbgruppe 56; 140

Hash-Funktion 282

Heap 76

I

Identifikation 172; 277

Identifikationsschema

nach Fiat-Shamir 172

ifstream 262

inc_I 23

Induktion

vollstiindige 5

Information-Hiding 219

Inkrement 23

Internet 175; 277

inv_1 146

Inverses

modulo einer Zweierpotenz 92

irooU 150

isprime_1 187

Index

J

Jacobi, Carl Gustav Jacob (1804-1851) Jacobi-Symbol 153; 154; 155; 157; 182;

247;295

jacobU 157

K

Karatsuba, A.

Verfahren zur Multiplikation 25; 31; 32

Kernfunktionen 59 kgV_1 139

Klasse LINT 221

RSAkey 286 RSApub 286

kmuU 32 Kommutativgesetz 5; 55 Kongruenz 53

lineare 192 Konstruktion

starker Primzahlen 280 Konstruktor 222; 225; 227 Korper

endlicher 142 Kryptoverfahren Siehe

Verschliisselungsverfahren Kurven

elliptische 297

L

LCLint 207 Id_1 148

Legendre, Adrien Marie (1752-1833) 3 Legendre-Symbol 152; 154

limits.h IO

LINT 221 LINT::add 239

LINT::chinrest 246

LINT::clearbit 244 LINT::divr 240 LINT::fswap 244

LINT::Gec Warning_Status 266 LINT::ggT 245

LINT::inv 245 LINT::iseven 243

LINT::isprime 248

LINT::jacobi 247 LINT::kgV 246

LINT::ld 245 LINT::madd 241

LINT::mequ 241

LINT::mexp 238 LINT::mexp2 242 LINT::mexp5m 243 LINT::mexpkm 243; 287 LINT::mmul 242 LINT: :mod 240

LINT::mod2 241 LINT::msqr 242

LINT::msub 242 LINT::mul 240 LINT::root 247; 248

LINT::SeCLINT.-ETTor_Handler 268 LINT::setbit 244

LINT::shift 243 LINT::sqr 240

LINT::sub 239 LINT::testbit 244 LINT::xggT 246 LINT::zweianteil 248

LINT -Operatoren 230 Iittle-endian 260 Logarithmus 147 Isdptr_1 18

M

madd_l 60

malloc 212 Manipulator 257; 258

member-Funktionen 237 Menge

leere 3

mequ_1 64 Mersenne, Marin (1588-1648)

Mersenne-Primzahlen 175 mexp2_1 81 mexp5m_1 93

325

326

mexpk_1 76

Miller-Rabin-Test 183

mmuU 62 mod_1 49

mod2_1 50

Modulus 277; 287

Monte Carlo-Methoden 191

Montgomery-Potenzierung 93; 287

Montgomery-Produkt 87

Montgomery-Quadrierung 92

Montgomery-Reduktion 87

msdptr_1 18

msqr_1 63

msub_1 61

mul58

muU 28; 58; 59

mulmon_1 90

Multiplikation 25; 58; 99; 101

modulare 57

von Restklassen 54

N

Nachfolger 4

Nachfolgermenge 4

Newton

Methode von 148

Nichtrest

quadrati scher lSI

NP 83; lSI; 164

NP-vollstandig 83

nuU 12

Null II

Nullen

ftihrende 14

o Objekt 219

of stream 260

one_I 12

or_1 107

p

P 83

panic 266; 268

Partia1produkt 26; 36; 39

PC-lint 207

Peano, Guiseppe (1858-1932)

Peano-Axiome 5

Peri ode einer Pseudozufallsfolge 193

Periodenl1inge

maximale 193

Phi-Funktion 142

Potenz 6

Potenzierung

Fenster-Methoden 84

modulare 65; 98; 180

Montgomery- 93

Potenzregeln 65; 213

prime_I 187

Primitivwurzel modulo p 96

primwurz_1 97

Primzahl(en) 174; 277

Erkennung von 176

griiBte bekannte 175

starke 279

Primzahlen

gespeichert in small primes 185

Primzahlsatz 179

Primzahltest

deterministischer 190

nach Miller-Rabin 183

von Solovay-Strassen 182

Produkt 5

Programmierung

objektorientierte 221

prooU 161

Protokoll

Index

Authentisierung nach Fiat-Shamir 172

Diffie-Hellman-Schliisselaustausch 96

digitale Signatur mit RSA 282

RSA-Verschliisselung 278

Pseudoprimzahl 181

starke 183

Pseudozufallszahlen 191

purge_I 131

Index

purge_reg_1 129 purgeall_reg_1 129

Q Quadratwurzel

ganzzahliger Anteil 147 Quadrierung 34; 35; 36; 38

modulare 57 Quotient 38; 39; 102

R

rand_I 200

rand64_1 197

randbiU 201 Raphson Siehe Newton

Reduzierung modulo m 57; 58 Rest 39; 54; 57

quadratischer 151 Restklasse 54 Restklassengruppe

prime 142 Restklassenring 57

ResTrack 212 Restsystem

vollstiindiges 56

Reziprozitiitsgesetz 153 Riemann, G. F. Bernhard (1826-1866)

Riemann'sche Hypothese 161

Ring 54; 55 kommutativer 54

rooU 166 RSA-Entschliisse)ung

schnelJe 287

RSA-Klasse 287 RSA-Schliisselpaar 277 RSA-Verfahren 94; 176; 275

Riickgabe

einer Funktion 13

s Schliisselaustausch

nach Diffie-HelJman 96

Schliisselkomponente geheime 277 offentliche 277

Schliisselliingen flir RSA 280

seed64_1 198

seedBBS_1 201 Semaphor 127

secnoofregs_1 128

setbiU 110 sfactor_1 187 Shamir, Adi 172

shifU 102

shU 101 shel 102 Sieb des Eratosthenes 176; 177 sieve_I 185

Signatur digitale 94; 276 verdeckte 283

Signaturgesetz 277 smaIlprimes 185 sqr 58 sqr_1 36; 58 Stack 8; 76

Stapelspeicher 8 str2clinU 119

Stroustrup, Bjarne 219

sub 58 sub_I 21; 58

Subsystem 122 Subtraktion 20; 39

modulare 57

von Restklassen 55 Summe 5

T

template

omanip<T> 259

testbiU III Testplan 209

Testsuite 214

throw 269 try-Block 269 two_I 12

327

328

u uadd_1 22

Uberlauf

arithmetischer 14; 20; 23; 58

Ubertrag 17

udiv_l 49

ul2clinU 122

ulrand64_1 199

ulrandBBS I 202

ulseed64_1 198

umadd_1 63

umexp_1 66

umod_1 51

umul 58

umuU 30

Unendlichkeitsaxiom 4

Unterlauf

arithmetischer 14; 20; 23; 58; 100

usub_1 23

v vcheck_1 123

Verkniipfungstabellen 57

Verschliisselung 57

Verschliisselungsverfahren

asymmetrische 95; 275

Public-Key 95

Vertreter

einer Restklasse 54

Vielfaches

kleinstes gemeinsames 139

Vorglinger 4

Index

Vorperiode einer Pseudozufallsfolge 193

w wmexp_l 68; 185

wmexpm_194

x xggT_I 144

xOf_1 108

z Zahl(en)

ganze 56; 321

natiirliche 4; 321

rationale 56

Zero-Knowledge-Verfahren 173

Zertifikat 284

Zertifizierungsinstanz 284

zweianteU 156

Zweianteil einer Zahl 156

Zykel einer Pseudozufallsfolge 193

Riicknahme oder Umtausch nur mit ungeOffneter Datentragerverpackung

Voraussetzungen

Rechner mit installiertem Coder c++ Computer entsprechend dem ANSI/ISO Standard.