- cypherpunks-legacy - lists.cpunks.org

LUC Public Key Crypto...
by Jim Choate 17 Dec '03

17 Dec '03

Hi, In the process of doing some research on Gauss I stumbled across this... ____________________________________________________________________ | | | Those who make peaceful revolution impossible will make | | violent revolution inevitable. | | | | John F. Kennedy | | | | | | _____ The Armadillo Group | | ,::////;::-. Austin, Tx. USA | | /:'///// ``::>/|/ http://www.ssz.com/ | | .', |||| `/( e\ | | -====~~mm-'`-```-mm --'- Jim Choate | | ravage(a)ssz.com | | 512-451-7087 | |____________________________________________________________________| Forwarded message: > Dr. Dobb's Web Site > > LUC PUBLIC-KEY ENCRYPTION > > > > A secure alternative to RSA > > Peter Smith > > Peter has worked in the computer industry for 15 years as a > programmer, analyst, and consultant and has served as deputy editor of > Asian Computer Monthly. Peter's interest in number theory led to the > invention of LUC in 1991. He can be reached at 25 Lawrence Street, > Herne Bay, Auckland, New Zealand. > > > _________________________________________________________________ > > According to former NSA director Bobby Innman, public-key cryptography > was discovered by the National Security Agency in the early seventies. > At the time, pundits remarked that public-key cryptography (PKC) was > like binary nerve gas--it was potent when two different substances > were brought together, but quite innocuous in its separate parts. > Because the NSA promptly classified it, not much was known about PKC > until the mid-seventies when Martin Hellman and Whitfield Diffie > independently came up with the notion and published papers about it. > > Traditional cryptographic systems like the venerable Data Encryption > Standard (DES) use the same key at both ends of a message > transmission. The problem of ensuring correct keys leads to such > expensive expedients as distributing the keys physically with trusted > couriers. Diffie and Hellman (and the NSA) had the idea of making the > keys different at each end. In addition to encryption, they envisioned > this scheme would also lead to a powerful means of source > authentication known as digital signatures. > > RSA, developed in 1977, was the first reliable method of source > authentication. The RSA approach (patented in the early eighties) > initiated intense research in "number theory," one of the most > recondite areas of mathematics. Although C.F. Gauss studied this topic > in the early 1800s (referring to it then as "higher arithmetic"), very > little real progress has been made in solving the problem of factoring > since then. The means available today are essentially no better than > exhaustive searching for prime factors. In terms of intractability > theory, however, no one has yet proved that the problem is > intractable, although researchers believe it to be so. > > > > The RSA Algorithm > > > > RSA works by raising a message block to a very large power, then > reducing this modulo N, where N (the product of two large prime > numbers) is part of the key. Typical systems use an N of 512 bits, and > the exponent to which blocks are raised in decryption is of the same > order. An immediate problem in implementing such a system is the > representation and efficient manipulation of such large integers. > (Standard microprocessors don't really have the power to handle normal > integer sizes and functions; even numeric coprocessors are inadequate > when integers of this size are involved.) > > RSA has dominated public-key encryption for the last 15 years as > research has failed to turn up a reliable alternative--until the > advent of LUC. Based on the same difficult mathematical problem as > RSA, LUC uses the calculation of Lucas functions instead of > exponentiation. (See text box entitled, "How the Lucas Alternative > Works.") > > Because we're working in the area of mathematics, we can formally > prove that LUC is a true alternative to RSA. Furthermore, we can show > that a cipher based on LUC will be at least as efficient. More > importantly, we can show that LUC is a stronger cipher than RSA. The > reason is that under RSA, the digital signature of a product is the > product of the signatures making up the product; in mathematical > terms, M{e}L{e}=(ML){e}. This opens RSA to a cryptographic attack > known as adaptive chosen-message forgery. Ironically, this is outlined > in a paper co-authored by Ron Rivest (the "R" in RSA). LUC is not > multiplicative and therefore not susceptible to this attack. Using > Lucas functions, V[e](M,1)V[e](L,1) is not equal to V[e](ML,1). In > other words, the use of exponentiation leads to RSA being > multiplicative in this way, while LUC's use of Lucas functions avoids > this weakness. > > Choosing the Algorithms > > > > Lucas functions have been studied mainly in relation to primality > testing, and it was to these sources we turned when researching > efficient algorithms for implementing LUC. For given parameters, the > Lucas functions give rise to two series, U[n] and V[n]. The first > algorithm (see Listing One, page 90) calculated both, even though we > were only interested in V[n]. It was only in a paper on factoring > integers that we found a means of calculating V[n] alone (see Listing > Two, page 90). The pseudocode examples show that both algorithms have > two phases: The work done when the current bit is a 0 is half the work > necessary when the current bit is a 1. > > More Details. > > Typically, in systems like LUC the exponent used for encryption is a > much smaller integer than that used for decryption. A commonly chosen > encryption exponent is the prime number 65,537. This is a good choice > for fast encryption as all but 2 of the 17 bits are 0s. We have no > such control over the decryption exponent, but there is a way of > halving the work, and thus, of introducing a limited degree of > parallelism into the calculation. > > Since LUC is a public-key cryptosystem, we can always assume that the > possessor of the private decrypting keys knows the two primes (p and > q) which make up the modulus, N. Consequently, we can reduce the > exponent and message with respect to the two primes, in each case at > least halving the amount of work. At the end of the calculation with > respect to the primes, we bring the results together to produce the > final plain text (see Listing Three, page 90). > > Large-integer Arithmetic > > > > There's really only one source of information about large-integer > arithmetic: Knuth's The Art of Computer Programming. We found that > almost every time we referred to his book, we came up with some new > angle or way of tweaking some extra performance out of our code. > > We decided to represent the large integers as 256-byte arrays, with > the low byte giving the length (in bytes) of the integer. For > instance, the 8-byte hexadecimal number 1234567890ABCDEF would appear > in a file view as 08 EF CD AB 90 78 56 34 12. These arrays became a > Pascal-type har (for hexadecimal array). We can store integers of over > 600 decimal digits in our hars, but because the hars must be able to > hold the results of a multiplication, we are limited to manipulating > integers up to 300 decimal digits in length. > > Implementation of addition, subtraction, and multiplication went quite > smoothly; implementation of division took more effort. (We took > comfort in not being the first to encounter problems with division. > Lady Ada Lovelace, the first computer programmer, said, "I am still > working at some most entangled notations of division, but see my way > through them at the expense of heavy labor, from which I shall not > shrink as long as my head can bear it.") We tried various methods, > including one based on Newton which calculated the inverse of the > divisor and then multiplied. (See Knuth's discussion.) We finally > opted for Knuth's Algorithm D, despite his warning that it contained > possible discontinuities. At that stage, we were working on a 16-bit > 80286 PC; see Listing Four, page 90. > > Of course there was much more than the division routine to consider, > but we found that it was the critical routine in terms of getting LUC > to run at a reasonable speed. Once we had upgraded to an 80386, we > converted to a full 32-bit implementation. The assembler code for the > division (still Algorithm D) is given in Listing Five (page 91). > Although space constraints prevent a complete presentation of the > code, suffice to say that we have been able to achieve a > signing/decryption speed on a modulus of 512 bits of over 200 bits per > second (33-MHz 80386, 0 wait states). > > Other Issues > > > > Central to any cryptographic system are keys. In LUC, if an adversary > is able to find p and q, the prime factors of modulus N, then all > messages sent with N can be either read in the case of encryption or > forged in the case of signing. > > Since the days of Gauss, research on factoring has come up with > various so-called "aleatoric" methods of factoring some numbers. These > methods are like cures for poison ivy: numerous, and occasionally > efficacious. One old method, found by Pierre Fermat, is very quick at > factoring some types of composite numbers. If N is the product of two > primes which are close together, then it can be easily factored. For > example, if p=1949, and q=1951, then N=3802499. Taking the square root > of N, we find that it is approximately 1949.999. Adding 1 to the > integral part of this (giving 1950), we square this, giving 3802500. > If we now subtract N from this square, we get a difference of 1, which > is the square of itself. This means that N has been expressed as the > difference of two squares. As we learned in high school, x{2}-y{2} = > (x-y)(x+y), and so we obtain the two factors. > > Fermat's method works whenever the ratio of the factors is close to an > integer. (Note that the ratio is close to 1 in the above discussion.) > This attack, as cryptographers call methods used to break a cipher, > has to be guarded against in generating the modulus N. > > Another guard is that neither (p + 1) and (q + 1) nor (p - 1) and (q - > 1) should be made up of small prime factors. There are many other > guards of varying degrees of importance, but the entire area needs > consideration depending on the level of security required, and how > long the keys are meant to last. > > The basic idea behind LUC is that of providing an alternative to RSA > by substituting the calculation of Lucas functions for that of > exponentiation. While Lucas functions are somewhat more complex > mathematically than exponentiation, they produce superior ciphers. > > This substitution process can be done with systems other than the RSA. > Among these are the Hellman-Diffie-Merkle key exchange system (U.S. > Patent number 4,200,770), the El Gamal public-key cryptosystem, the El > Gamal digital signature, and the recently proposed Digital Signature > Standard (DSS), all of which use exponentiation. > > The nonmultiplicative aspect of Lucas functions carries over, allowing > us to produce alternatives to all these. In the case of the DSS, Lucas > functions allow us to dispense with the one-way hashing cited (but not > specified) in the draft standard. > > A New Zealand consortium has been set up to develop and license > systems based on LUC, which is protected by a provisional patent. For > more information, contact me or Horace R. Moore, 101 E. Bonita, Sierra > Madre, California 91024. > > References > > > > Athanasiou, Tom. "Encryption Technology, Privacy, and National > Security." MIT Technology Review (August/September, 1986). > > Diffie, W. and M.E. Hellman. "New Directions in Cryptography." IEEE > Transactions on Information Theory (November, 1976). > > El Gamal, Taher. "A Public Key Cryptosystem and a Signature Scheme > Based on Discrete Logarithms." IEEE Transactions on Information Theory > (July, 1985). > > Gauss, C.F. "Disquisitiones Arithmeticae," Article 329. > > Goldwasser, S., S. Micali, and R. Rivest. "A Digital Signature Scheme > Secure Against Adaptive Chosen Message Attack." SIAM J. COMPUT (April, > 1988). > > Kaliski, Burton S., Jr. "Multiple-precision Arithmetic in C." Dr. > Dobb's Journal (August, 1992). > > Knuth, D.E. The Art of Computer Programming: Volume II: Semi-Numerical > Algorithms, second edition. Reading, MA: Addison-Wesley, 1981. > > Schneier, Bruce. "Untangling Public Key Cryptography." Dr. Dobb's > Journal (May, 1992). > > Williams, H.C. "A p + 1 method of factoring." Mathematics of > Computation (vol. 39, 1982). > > How the Lucas Alternative Works > > > > As with RSA encryption, use of the Lucas alternative involves two > public keys: N and e. The number N is assumed to be the product of two > large (odd) prime numbers, p and q. Encryption and decryption of a > message is achieved using Lucas sequences, which may be defined as > shown in Example 1. Note that P and Q are integers. > > If a message P is to be sent, it is encoded as the residue P1 modulo N > of the eth term of the Lucas sequence V[n](P,1), and then transmitted. > The receiver uses a secret key d (based on the prime factorization of > N) to decode the received message P1, by taking the residue modulo N > of the dth term of the Lucas sequence V[n](P1,1). The secret key d is > determined so that V[d](V[e](P,1),1) = P modulo N, ensuring the > decryption of the received message P1 as P. The existence of such a > key d is based on the following theorem. > > Theorem > > > > Suppose N is any odd positive integer, and P is any positive integer, > such as P{2}-4 is coprime to N. If r is the Lehmer totient function of > N with respect to D = P{2}-4 (see Example 2), then V[mr+1](P,1)=P > modulo N for every positive integer m. The condition that P{2}-4 be > coprime to N is easily checked, as P{2}-4=(P+2)(P-2). Also, because > V[d](V[e](P,1),1)=V[de](P,1), according to Example 4(e), the key d may > simply be chosen so that de=1 modulo r. > > The Lehmer Totient Function > > > > Suppose P and Q are integers, and a and b are the zeros of X{2}-Px+Q > (so that P = a+b while Q = ab). Also, let D be the discriminant of > x{2}-Px+Q. That is, D = P{2}-4Q = (a-b){2}. > > The Lucas sequences U[n] = U[n] (P,Q) and V[n] = V[n] (P,Q) are > defined for n = 0,1,2, and so on by the equation in Example3. > > In particular, U[0] = 0, U[1] = 1, and then U[n+1] = PU[n] - QU[n-1] > (for n = 1,2,3,...), while V[0] = 2, V[1] = P, and similarly V[n+1]= > PV[n]-QV[n-1] (for n = 1,2,3,...). These sequences satisfy a number of > identities, including the following which may be simply obtained from > the definitions in Example 4. > > Next, suppose N is any positive integer, and let r be the Lehmer > totient function of N with respect to D = P{2}-4Q, defined the same > way as in the statement of the theorem. In the special case where N is > an odd prime p, the Lehmer totient function of p with respect to D is > the number given by the equation in Example 5(a). In this case, the > Lucas-Lehmer theorem states that if p does not divide Q then the > equation in Example 5(b) holds true. > > Example of LUC > > > > Let N = pxq = 1949x2089=4071461, and P = 11111, which equals the > message to encrypt/decrypt. The public keys will be e and N; the > private key will be d. First, calculate r, the Lehmer totient function > of P with respect to N. To do this we need to calculate the Legendre > of p and q. Let D = p{2}-4; then (D/1949) =-1 and (D/2089)=-1 are the > two Legendre values. Hence r is the least common multiple of 1949 + 1 > and 2089 + 1; see Example 6(a). Choosing e = 1103 for our public key, > we use the Extended Euclidean Algorithm to find the secret key d, by > solving the modular equation ed = 1 mod r. d turns out to equal 24017. > > To encrypt the message 11111, we make the calculation shown in Example > 6(b). To decrypt the encrypted message, we calculate as in Example > 6(c). --P.S. > > > _LUC PUBLIC-KEY ENCRYPTION_ > by Peter Smith > > > [LISTING ONE] > > { To calculate Ve(P,1) modulo N } > Procedure LUCcalc; > {Initialise} > BEGIN > D := P*P - 4; ut := 1; vt := P; u := ut; v := vt; > If not odd(e) then BEGIN u := 0; v := 2; END; > e := e div 2; > {Start main} > While e > 0 do > BEGIN > ut := ut*vt mod N; vt := vt*vt mod N; > If vt < 3 then vt := vt + N; > vt := vt - 2; > If odd(e) then > BEGIN > c := (ut*v + u*vt) mod N; > v := (vt*v + D*u*ut) mod N; > If odd(v) then v := v + N; v := v/2; > If odd(c) then c := c + N; u := c/2; > END; > e := e div 2; > END; > END; {LUCcalc} > > { The required result is the value of v.} > > > > > > > [LISTING TWO] > Pseudocode for calculating Lucas Functions > > Procedure wiluc { V = V(M) Mod N, the Mth Lucas number(P,1) } > Var > V,Vb,P,Vf,N,M,NP, Vd, Vf : LargeInteger ; > carry, high_bit_set : boolean ; > bz : word ; > BEGIN > Va := 2 ; { V[0] } Vb = P ; { V[1] } > NP := N - P; bz := bits(M) -1 ; { test bits from high bit downwards } > For j := 1 to bz do > BEGIN > Vc := Vb * Vb; Vf = Vc ; If Vf < 2 then Vf := Vf + N > Vf := Vf - 2; Vd := Va * Vb > { Vc := V, Vd := V*Vb, Vf := V-2} > If high_bit_set Then > BEGIN > Vb := P * Vc; If Vb < Vd then Vb := Vb + N; Vb := Vb - Vd; > If Vb < P then Vb := Vb + N; Vb := Vb - P; Va := Vf > END ; > Else BEGIN { "even" ie high bit not set } > Va := Vd; If Va < P then Va := Va + N; Va := Va - P; > Vb := Vf; > END ; > High_bit_set := next_bit_down(M); > {This boolean function determines the setting of the next bit down} > Va := Va Mod N; Vb := Vb Mod N > END ; { for j to bz } > END ; {wiluc} > > > > > > > [LISTING THREE] > > { Pseudocode for splitting decryption/signing over p and q > (N = p*q) } > Procedure hafluc ( var s,p,q,m,e : LargeInteger ; qix : word ) ; > var ep,emq, > temp,pi,qi, > b,n,pa,qa : LargeInteger ; > > { This procedure applies only to decipherment and signing, where the primes > making up the modulus N ( = p * q) are known (or can be easily deduced, > since both keys are known). Applying it allows us to halve the amount of > work. Encipherment is usually done with a small key - standard is 65537. } > Begin > Qpr (pa,qa,p,q,m,qix ) ; {} {assumes qix already calculated } > ep = e ; ep = ep Mod pa > emq = e ; emq = emq Mod qa > mp = m ; mp = mp Mod p > mq = m ; mq = mq Mod q > wiluc(q2,mq,emq,q) ; wiluc(p2,mp,ep,p) ; > if p2 < q2 then > Begin > temp = q q = p p = temp > temp = q2 q2 = p2 p2 = temp > End ; > temp = p2 temp = temp - q2 > n = p * q > { Solve with Extended Euclidean algorithm qi = 1/q Mod p. The algorithm > for the Extended Euclidean calculation can be found in Knuth. } > r = temp * p > r = r mod N > s = r * qi > s = s Mod n > s = s + p2 > End ; { hafluc } > Procedure SignVerify ; > Begin > h4 = 4 > p = large prime... > q = large prime... > n = p * q > bz := bits(n) ; > {write(cf,' generate 4 keysets (d,e) for p1,q1') ;} > { > qix table for T[qix] > Convention for qix > This calculation is explained below. > Lehmer totient qix Legendre values for p and q > i.e. T[qix] = LCM > (p - 1),(q - 1) 1 1 1 > (p - 1),(q + 1) 2 1 -1 > (p + 1),(q - 1) 3 -1 1 > (p + 1),(q + 1) 4 -1 -1 > e = encryption key, small prime eg 65537 > mu = message as large integer less than n > Solve e * d[qix] = 1 Mod T[qix] using Extended Euclidean Algorithm > where T[qix] is lcm(p1,q1), the Lehmer totient function of N > with repect to mu, according to the above table. > This gives 4 possible values of d, the decryption/signing key. > The particular value used depends on the message mu, as follows: > Let D = mu2 - 4. Calculate the Legendre values of D with respect to > both p and q. This value is -1 if D is a quadratic non-residue of > p (or q), and equal to 1 if D is a quadratic residue of p (or q). > N.B. This part is the most difficult part of LUC! Take care. > > Signing (Deciphering): > hafluc (a,pu,qu,mu,d,qix) > > Verifying (Enciphering): > Use Wiluc. > End. > > > > > > > [LISTING FOUR] > > Algorithm D in 32-bit Intel assmbler > Author: Christopher T. Skinner > Short version of Mod32.Txt with scalings just as comments > Modulus routine for Large Integers > u = u Mod v > Based on: > D.E.Knuth The Art of Computer Programming > Vol 2 Semi-Numerical Algorithms 2ed 1981 > Algorithm D page 257 > We use a Pascal Type called "har" ( for "hexadecimal array") > Type > har = Array[0..255] of byte ; > Var u,v : har ; > Note that u[0] is the length of u and that the > integer begins in u[1] > It is desirable that u[1] is on a double word boundary. > > ; Turbo Pascal Usage: ( Turbo Pascal v6.0) > ; {$L Mod32a} { contains mod32 far } > ; {$F+} { far pointers } > ; procedure Mod32 ( var u,v : har ) ; > ; Turbo Assembler code: (TASM v2.01)--requires 32-bit chip ie 386 or 486 > ; nb FS and GS can be used as temporary storage. Don't try to use them as > ; segment registers because Windows 3.0 restricts their allowed range, even > ; after you have finished out of Windows. You will hang for sure, unless you > ; have used a well-behaved protected-mode program to reset them, or cold boot. > > Data Segment Word Public Use16 > vdz dw ? ; size v words > va dd ? ; hi dword v > vb dd ? ; 2nd " v > vi dw ? ; ^v[1] > savdi dw ? ; used in addback > Data EndS > > Code Segment Word Public Use16 > Assume cs:Code, ds:Data ,es:Nothing > Public mod32 > ; Pascal Parameters: > u Equ DWord Ptr ss:[bp+10] ; Parameter 1 of 2 (far) > v Equ DWord Ptr ss:[bp+ 6] ; parameter 2 of 2 > uof equ word ptr ss:[bp+10] > vinof equ word ptr ss:[bp+ 6] > > mod32 Proc far > push bp > mov bp,sp > push di > push si > push ds ; save the DS > > ; Before using Mod32 check that: > ; v > 0 > ; v < u u <= 125 words > ; v[0] is a multiple of 4 and at least 8 > ; v[top] >= 80h (may need to scale u & v) > ; make u[0] = 0 Mod 4 (add 1..3 if required) > domod: > ; now point to our v > mov ax,seg v > mov ds,ax > assume ds:Data > mov si, offset v > cld > assume es:Nothing > xor ah,ah > mov al,es:[di] ; ax = size of u in bytes "uz" > mov cx,ax ; cx = uz > mov bx,ax ; bx = uz > mov al,[si] > mov dx,ax ; dx = size v bytes > shr ax,2 > mov vdz,ax ; vdz " dwords vz = 0 mod 4 > sub bx,dx ; bx = uz - vz difference in bytes > mov ax,bx ; ax = uz - vz > sub ax,3 ; ax = uz - vz - 3 -> gs > sub cx,3 ; cx = uz - 3 > add cx,di ; cx = ^top dword u > add ax,di > mov gs,ax ; gs = ^(uz-vz-3) u start (by -4 down to 1) > inc di > mov fs,di ; fs = uf = ^u[1] , end point > inc si > mov vi,si ; vi = ^v[1] > add si,dx > mov eax,[si-4] > mov va,eax ; va = high word of v > mov eax,[si-8] > mov vb,eax ; vb = 2nd highest word v > mov di,cx ; set di to ut , as at bottom of loop > d3: > mov edx,es:[di] ; dx is current high dword of u > sub di,4 > mov eax,es:[di] ; ax is current 2nd highest dword of u > mov ecx,va > cmp edx,ecx > jae aa ; if high word u is 0 , never greater than > div ecx ; mov ebx,eax > mov esi,edx ; si = rh > jmp short ad ; Normal route -- -- -- -- --> > aa: mov eax,0FFFFFFFFh > mov edx,es:[di] ; 2nd highest wrd u > jmp short ac > ab: mov eax,ebx ; q2 > dec eax > mov edx,esi ; rh > ac: mov ebx,eax ; q3 > add edx,ecx > jc d4 ; Knuth tests overflow, > mov esi,edx > ; normal route: > ad: > mul vb ; Quotient by 2nd digit of divisor > cmp edx,esi ; high word of product : remainder > jb d4 ; no correction to quot, drop thru to mulsub > ja ab ; nb unsigned use ja/b not jg/l > cmp eax,es:[di-4] ; low word of product : 3rd high of u > ja ab > d4: ; Multiply & subtract * * * * * * * > mov cx,gs > mov di,cx ; low start pos in u for subtraction of q * v > sub cx,4 > mov gs,cx > xor ecx,ecx > Mov cx,vdz ; word count for q * v > mov si,vi ; si points to v[1] > xor ebp,ebp ; carry 14Oct90 bp had problems in mu-lp > even > ; ** ** ** ** ** ** ** ** > ba: lodsd ; eax <- ds[si] > mul ebx ; dx:ax contains product carry set if dx > 0 > add eax,ebp > adc edx,0 > sub es:[di],eax > adc edx,0 > mov ebp,edx > add di,4 > loop ba ; dec cx , jmp if not 0 > ; .. .. .. . .. .. . .. .. . .. . . .. > sub es:[di],edx > jnc d7 > > mov si,vi ; add back (rare) > mov savdi,di > mov di,gs > add di,4 > clc > mov cx,vdz > bb: lodsd ; eax = ds[si] si + 2 > adc es:[di],eax > inc di > inc di > inc di > inc di > loop bb > xor eax,eax > mov es:[di],eax > mov di,savdi > ; test with: > ; 1,00000000,00000000,00000001/ 80000000,00000000,00000001 > d7: > mov bx,fs ; fs ^u[1] > mov ax,gs ; gs = current u start position > cmp ax,bx ; current - bottom > jb d8 > sub di,4 > jmp d3 > d8: > ; here we would scale u down if it had been scaled up > quex: ; quick exit if v < u > cld ; just in case > pop ds > pop si > pop di > pop bp > ret 8 ; 2 pointers = 4 words = 8 bytes > mod32 EndP ; > Code Ends > End > > > > > > [LISTING FIVE] > > Algorithm D in 16-bit Intel assembler > Author: Christopher T. Skinner > mod16.txt 21 Au8 92 16 bit modulus > ; divm Modulus > Data Segment Word Public > vwz dw ? ; size v words > va dw ? ; hi word v > vb dw ? ; 2nd " v > vi dw ? ; ^v[1] > uf dw ? ; ^u[3] > uz dw ? ; size u byte > vz dw ? ; " v " > ua dw ? ; ^( u[0] + uz - vz -1 ) , mul sub start > ut dw ? ; ^ u[topword] > qh dw ? > uzofs dw ? ; ttt > vzofs dw ? ; ttt > Data EndS > Code Segment Word Public > Assume cs:Code, ds:Data > Public diva > > u Equ DWord Ptr [bp+10] ; ES:DI > v Equ DWord Ptr [bp+6] ; DS:SI > ; NB v Must be Global, DS based... > diva Proc far > push bp > mov bp,sp > push ds > cld ; increment lodsw in mulsub > lds si,v > les di,u > xor ah,ah > mov al,es:[di] ; ax = uz size of u in bytes N.B. uz is not actually used > mov cx,ax ; cx = uz > mov bx,ax ; bx = uz > mov al,ds:[si] > mov dx,ax ; dx = size v bytes > shr ax,1 > mov vwz,ax ; vwz " words > sub bx,dx ; bx = uz - vz difference in bytes > mov ax,bx ; ax = uz - vz > dec ax ; ax = uz - vz - 1 -> ua > dec cx ; cx = uz - 1 > add cx,di ; cx = ^top word u > mov ut,cx ; ut = ^top word u > add ax,di > mov ua,ax ; ua = ^(uz-vz-1) u start (by -2 down to 1) > inc di > mov uf,di ; uf = ^u[1] , end point > inc si > mov vi,si ; vi = ^v[1] > add si,dx > mov ax,ds:[si-2] > mov va,ax ; va = high word of v > mov ax,ds:[si-4] > mov vb,ax ; vb = 2nd highest word v > mov di,cx ; set di to ut , as at bottom of loop > d3: > mov dx,es:[di] ; dx is current high word of u > dec di > dec di > mov ut,di > mov ax,es:[di] ; ax is current 2nd highest word of u > mov cx,va > cmp dx,cx > jae aa ;if high word u is 0 , never greater than > div cx ; > mov qh,ax > mov si,dx ; si = rh > jmp ad ; Normal route -- -- -- -- --> > aa: mov ax,0FFFFh > mov dx,es:[di] ; 2nd highest wrd u > jmp ac > ab: mov ax,qh > dec ax > mov dx,si ; rh > ac: mov qh,ax > add dx,cx > jc d4 ; Knuth tests overflow, > mov si,dx > ad: mul vb ; Quotient by 2nd digit of divisor > cmp dx,si ; high word of product : remainder > jb d4 ; no correction to quot, drop thru to mulsub > ja ab ; nb unsigned use ja/b not jg/l > cmp ax,es:[di-2] ; low word of product : 3rd high of u > ja ab > d4: ; Multiply & subtract * * * * * * * > mov bx,ua > mov di,bx ; low start pos in u for subtraction of q * v > dec bx > dec bx ; > mov ua,bx > Mov cx,vwz ; word count for q * v > mov si,vi ; si points to v[1] > mov bx,qh > xor bp,bp > ; ** ** ** ** ** ** ** ** > ba: lodsw ; ax <- ds[si] si + 2 preserve carry over mul ? > mul bx ; dx:ax contains product carry set if dx > 0 > add dx,bp > xor bp,bp > sub es:[di],ax > inc di > inc di > sbb es:[di],dx > rcl bp,1 > loop ba ; dec cx , jmp if not 0 > ; .. .. .. . .. .. . .. .. . .. . . .. > rcr bp,1 > jnc d7 > > mov si,vi ; add back (rare) > mov di,ua > inc di > inc di > clc > mov cx,vwz > bb: lodsw ; ax = ds[si] si + 2 > adc es:[di],ax > inc di > inc di > loop bb > mov cx,ut > add cx,4 > sub cx,di > shr cx,1 ; word length of u > bc: mov Word Ptr es:[di],0 > inc di > inc di > loop bc ; > dec di ; > dec di ; > clc > d7: > mov ax,uf > cmp ua,ax > jb d8 > dec di ; New these are suspicious, with an add back and a > dec di ; New > jmp d3 > d8: > cld ; just in case > pop ds > pop bp > ret 8 ; 2 pointers = 4 words = 8 bytes ??? > diva EndP ; > Code Ends > End > > > _________________________________________________________________ > > Copyright © 1998, Dr. Dobb's Journal > Dr. Dobb's Web Site Home Page -- Top of This Page > >

1 0

RB_Fermat.html
by Jim Choate 17 Dec '03

17 Dec '03

PIERRE DE FERMAT (1601 - 1665) From `A Short Account of the History of Mathematics' (4th edition, 1908) by W. W. Rouse Ball. While Descartes was laying the foundations of analytical geometry, the same subject was occupying the attention of another and not less distinguished Frenchman. This was Fermat. Pierre de Fermat, who was born near Montauban in 1601, and died at Castres on January 12, 1665, was the son of a leather-merchant; he was educated at home; in 1631 he obtained the post of councillor for the local parliament at Toulouse, and he discharged the duties of the office with scrupulous accuracy and fidelity. There, devoting most of his leisure to mathematics, he spent the remainder of his life - a life which, but for a somewhat acrimonious dispute with Descartes on the validity of certain analysis used by the latter, was unruffled by any event which calls for special notice. The dispute was chiefly due to the obscurity of Descartes, but the tact and courtesy of Fermat brought it to a friendly conclusion. Fermat was a good scholar, and amused himself by conjecturally restoring the work of Apollonius on plane loci. Except a few isolated papers, Fermat published nothing in his lifetime, and gave no systematic exposition of his methods. Some of the most striking of his results were found after his death on loose sheets of paper or written in the margins of works which he had read and annotated, and are unaccompanied by any proof. It is thus somewhat difficult to estimate the dates and originality of his work. He was constitutionally modest and retiring, and does not seem to have intended his papers to be published. It is probable that he revised his notes as occasion required, and that his published works represent the final form of his researches, and therefore cannot be dated much earlier than 1660. I shall consider separately (i) his investigations in the theory of numbers; (ii) his use in geometry of analysis and of infinitesimals; and (iii) his method for treating questions of probability. (i) The theory of numbers appears to have been the favourite study of Fermat. He prepared an edition of Diophantus, and the notes and comments thereon contain numerous theorems of considerable elegance. Most of the proofs of Fermat are lost, and it is possible that some of them were not rigorous - an induction by analogy and the intuition of genius sufficing to lead him to correct results. The following examples will illustrate these investigations. (a) If p be a prime and a be prime to p then a^(p-1) - 1 is divisible by p, that is, a^(p-1) - 1 \equiv 0 (mod p). A proof of this, first given by Euler, is well known. A more general theorem is that a^(\phi(n)) - 1 \equiv 0 (mod n) (mod n), where a is prime to n and \phi(n) is the number of integers less than n and prime to it. (b) An odd prime can be expressed as the difference of two square integers in one and only one way. Fermat's proof is as follows. Let n be the prime, and suppose it equal to x² - y², that is, to (x + y)(x - y). Now, by hypothesis, the only integral factors of n are n and unity, hence x + y = n and x - y = 1. Solving these equations we get x = œ (n + 1) and y = œ (n - 1). (c) He gave a proof of the statement made by Diophantus that the sum of the squares of two integers cannot be of the form 4n - 1; and he added a corollary which I take to mean that it is impossible that the product of a square and a prime of the form 4n - 1 [even if multiplied by a number prime to the latter], can be either a square or the sum of two squares. For example, 44 is a multiple of 11 (which is of the form 4 × 3 - 1) by 4, hence it cannot be expressed as the sum of two squares. He also stated that a number of the form a² + b², where a is prime to b, cannot be divided by a prime of the form 4n - 1. (d) Every prime of the form 4n + 1 is expressible, and that in one way only, as the sum of two squares. This problem was first solved by Euler, who shewed that a number of the form 2^m (4n + 1) can be always expressed as the sum of two squares. (e) If a, b, c, be integers, such that a² + b² = c², then ab cannot be a square. Lagrange gave a solution of this. (f) The determination of a number x such that x²n + 1 may be a square, where n is a given integer which is not a square. Lagrange gave a solution of this. (g) There is only one integral solution of the equation x² + 2 = y³; and there are only two integral solutions of the equation x² + 4 = y³. The required solutions are evidently for the first equation x = 5, and for the second equation x = 2 and x = 11. This question was issued as a challenge to the English mathematicians Wallis and Digby. (h) No integral values of x, y, z can be found to satisfy the equation x^n + y^n = z^n ; if n be an integer greater than 2. This proposition has acquired extraordinary celebrity from the fact that no general demonstration of it has been given, but there is no reason to doubt that it is true. Probably Fermat discovered its truth first for the case n = 3, and then for the case n = 4. His proof for the former of these cases is lost, but that for the latter is extant, and a similar proof for the case of n = 3 was given by Euler. These proofs depend on shewing that, if three integral values of x, y, z can be found which satisfy the equation, then it will be possible to find three other and smaller integers which also satisfy it: in this way, finally, we shew that the equation must be satisfied by three values which obviously do not satisfy it. Thus no integral solution is possible. It would seem that this method is inapplicable to any cases except those of n = 3 and n = 4. Fermat's discovery of the general theorem was made later. A proof can be given on the assumption that a number can be resolved into the product of powers of primes in one and only one way. The assumption has been made by some writers; it is true of real numbers, but it is not necessarily true of every complex number. It is possible that Fermat made some erroneous supposition, but, on the whole, it seems more likely that he discovered a rigorous demonstration. In 1823 Legendre obtained a proof for the case of n = 5; in 1832 Lejeune Dirichlet gave one for n = 14, and in 1840 Lamé and Lebesgue gave proofs for n = 7. The proposition appears to be true universally, and in 1849 Kummer, by means of ideal primes, proved it to be so for all numbers except those (if any) which satisfy three conditions. It is not certain whether any number can be found to satisfy these conditions, but there is no number less than 100 which does so. The proof is complicated and difficult, and there can be no doubt is based on considerations unknown to Fermat. I may add that, to prove the truth of the proposition, when n is greater than 4 obviously it is sufficient to confine ourselves to cases when n is a prime, and the first step in Kummer's demonstration is to shew that one of the numbers x, y, z must be divisible by n. The following extracts, from a letter now in the university library at Leyden, will give an idea of Fermat's methods; the letter is undated, but it would appear that, at the time Fermat wrote it, he had proved the proposition (h) above only for the case when n = 3. Je ne m'en servis au commencement qe pour demontrer les propositions negatives, comme par exemple, qu'il n'y a aucu nombre moindre de l'unité qu'un multiple de 3 qui soit composé d'un quarré et du triple d'un autre quarré. Qu'il n'y a aucun triangle rectangle de nombres dont l'aire soit un nombre quarré. La preuve se fait par apagogeen en cette manière. S'il y auoit aucun triangle rectangle en nombres entiers, qui eust son aire esgale à un quarré, il y auroit un autre triangle moindre que celuy la qui auroit la mesme proprieté. S'il y en auoit un second moindre que le premier qui eust la mesme proprieté il y en auroit par un pareil raisonnement un troisieme moindre que ce second qui auroit la mesme proprieté et enfin un quatrieme, un cinquieme etc. a l'infini en descendant. Or est il qu'estant donné un nombre il n'y en a point infinis en descendant moindres que celuy la, j'entens parler tousjours des nombres entiers. D'ou on conclud qu'il est donc impossible qu'il y ait aucun triangle rectange dont l'aire soit quarré. Vide foliu post sequens.... Je fus longtemps sans pouvour appliquer ma methode aux questions affirmatives, parce que le tour et le biais pour y venir est beaucoup plus malaisé que celuy dont je me sers aux negatives. De sorte que lors qu'il me falut demonstrer que tout nombre premier qui surpasse de l'unité un multiple de 4, est composé de deux quarrez je me treuvay en belle peine. Mais enfin une meditation diverses fois reiterée me donna les lumieres qui me manquoient. Et les questions affirmatives passerent par ma methods a l'ayde de quelques nouveaux principes qu'il y fallust joindre par necessité. Ce progres de mon raisonnement en ces questions affirmatives estoit tel. Si un nombre premier pris a discretion qui surpasse de l'unité un multiple de 4 n'est point composé de deux quarrez il y aura un nombre premier de mesme nature moindre que le donné; et ensuite un troisieme encore moindre, etc. en descendant a l'infini jusques a ce que vous arriviez au nombre 5, qui est le moindre de tous ceux de cette nature, lequel il s'en suivroit n'estre pas composé de deux quarrez, ce qu'il est pourtant d'ou on doit inferer par la deduction a l'impossible que tous ceux de cette nature sont par consequent composez de 2 quarrez. Il y a infinies questions de cette espece. Mais il y en a quelques autres que demandent de nouveaux principes pour y appliquer la descente, et la recherche en est quelques fois si mal aisée, qu'on n'y peut venir qu'avec une peine extreme. Telle est la question suivante que Bachet sur Diophante avoüe n'avoir jamais peu demonstrer, sur le suject de laquelle Mr. Descartes fait dans une de ses lettres la mesme declaration, jusques la qu'il confesse qu'il la juge si difficile, qu'il ne voit point de voye pour la resoudre. Tout nombre est quarré, ou composé de deux, de trois, ou de quatre quarrez. Je l'ay enfin rangée sous ma methode et je demonstre que si un nombre donné n'estoit point de cette nature il y en auroit un moindre que ne le seroit par non plus, puis un troisieme moindre que le second etc. a l'infini, d'ou l'on infere que tous les nombres sont de cette nature.... J'ay ensuit consideré questions que bien que negatives ne restent pas de recevoir tres-grande difficulté, la methods pour y pratiquer la descente estant tout a fait diverse des precedentes comme il sera aisé d'espouver. Telles sont les suivantes. Il n'y a aucun cube divisible en deux cubes. Il n'y a qu'un seul quarré en entiers que augmenté du binaire fasse un cube, ledit quarré est 25. Il n'y a que deux quarrez en entiers lesquels augmentés de 4 fassent cube, lesdits quarrez sont 4 et 121.... Apres avoir couru toutes ces questions la plupart de diverses (sic) nature et de differente façon de demonstrer, j'ay passé a l'invention des regles generales pour resoudre les equations simples et doubles de Diophante. On propose par exemple 2 quarr. + 7957 esgaux a un quarré (hoc est 2xx + 7967 \propto quadr.) J'ay une regle generale pour resoudre cette equation si elle est possible, on decouvrir son impossibilité. Et ainsi en tous les cas et en tous nombres tant des quarrez que des unitez. On propose cette equation double 2x + 3 et 3x + 5 esgaux chaucon a un quarré. Bachet se glorifie en ses commentaires sur Diophante d'avoir trouvé une regle en deux cas particuliers. Je me donne generale en toute sorte de cas. Et determine par regle si elle est possible ou non.... Voila sommairement le conte de mes recherches sur le sujet des nombres. Je ne l'ay escrit que parce que j'apprehende que le loisir d'estendre et de mettre au long toutes ces demonstrations et ces methodes me manquera. En tout cas cette indication seruira aux sçauants pour trouver d'eux mesmes ce que je n'estens point, principlement si Mr. de Carcaui et Frenicle leur font part de quelques demonstrations par la descente que je leur ay envoyees sur le suject de quelques propositions negatives. Et peut estre la posterité me scaure gré de luy avoir fait connoistre que les anciens n'ont pas tout sceu, et cette relation pourra passer dans l'esprit de ceux qui viendront apres moy pour traditio lampadis ad filios, comme parle le grand Chancelier d'Angleterre, suivant le sentiment et la devise duquel j'adjousteray, multi pertransibunt et augebitur scientia. (ii) I next proceed to mention Fermat's use in geometry of analysis and of infinitesimals. It would seem from his correspondence that he had thought out the principles of analytical geometry for himself before reading Descartes's Géométrie, and had realised that from the equation, or, as he calls it, the ``specific property,'' of a curve all its properties could be deduced. His extant papers on geometry deal, however, mainly with the application of infinitesimals to the determination of the tangents to curves, to the quadrature of curves, and to questions of maxima and minima; probably these papers are a revision of his original manuscripts (which he destroyed), and were written about 1663, but there is no doubt that he was in possession of the general idea of his method for finding maxima and minima as early as 1628 or 1629. He obtained the subtangent to the ellipse, cycloid, cissoid, conchoid, and quadratrix by making the ordinates of the curve and a straight line the same for two points whose abscissae were x and x - e; but there is nothing to indicate that he was aware that the process was general, it is probable that he never separated it, so to speak, from the symbols of the particular problem he was considering. The first definite statement of the method was due to Barrow, and was published in 1669. Fermat also obtained the areas of parabolas and hyperbolas of any order, and determined the centres of mass of a few simple laminae and of a paraboloid of revolution. As an example of his method of solving these questions I will quote his solution of the problem to find the area between the parabola y³ = p x², the axis of x, and the line x = a. He says that, if the several ordinates of the points for which x is equal to a, a(1 - e), a(1 - e)²,... be drawn, then the area will be split into a number of little rectangles whose areas are respectively ae(pa^2)^(1/3), ae(1-e) ( pa^2(1-e)^2 )^(1/3),... . The sum of these is p^(1/3) a^(5/3) e / ( 1 - (1 - e)^(5/3) ) ; and by a subsidiary proposition (for he was not acquainted with the binomial theorem) he finds the limit of this, when e vanishes, to be (3/5) p^(1/3) a^(5/3) . The theorems last mentioned were published only after his death; and probably they were not written till after he had read the works of Cavalieri and Wallis. Kepler had remarked that the values of a function immediately adjacent to and on either side of a maximum (or minimum) value must be equal. Fermat applied this principle to a few examples. Thus, to find the maximum value of x(a - x), his method is essentially equivalent to taking a consecutive value of x, namely x - e where e is very small, and putting x(a - x) = (x - e)(a - x + e). Simplifying, and ultimately putting e = 0, we get x = œ. This value of x makes the given expression a maximum. (iii) Fermat must share with Pascal the honour of having founded the theory of probabilities. I have already mentioned the problem proposed to Pascal, and which he communicated to Fermat, and have there given Pascal's solution. Fermat's solution depends on the theory of combinations, and will be sufficiently illustrated by the following example, the substance of which is taken from a letter dated August 24, 1654, which occurs in the correspondence with Pascal. Fermat discusses the case of two players, A and B, where A wants two points to win and B three points. Then the game will be certainly decided in the course of four trials. Take the letters a and b, and write down all the combinations that can be formed of four letters. These combinations are 16 in number, namely, aaaa, aaab, aaba, aabb; abaa, abab, abba, abbb; baaa, baab, baba, babb; bbaa, bbab, bbba, bbbb. Now every combination in which a occurs twice or oftener represents a case favourable to A, and every combination in which b occurs three times or oftener represents a case favourable to B. Thus, on counting them, it will be found that there are 11 cases favourable to A, and 5 cases favourable to B; and since these cases are all equally likely, A's chance of winning the game is to B's chance as 11 is to 5. The only other problem on this subject which, as far as I know, attracted the attention of Fermat was also proposed to him by Pascal, and was as follows. A person undertakes to throw a six with a die in eight throws; supposing him to have made three throws without success, what portion of the stake should he be allowed to take on condition of giving up his fourth throw? Fermat's reasoning is as follows. The chance of success is 1/6, so that he should be allowed to take 1/6 of the stake on condition of giving up his throw. But if we wish to estimate the value of the fourth throw before any throw is made, then the first throw is worth 1/6 of the stake; the second is worth 1/6 of what remains, that is 5/36 of the stake; the third throw is worth 1/6 of what now remains, that is, 25/216 of the stake; the fourth throw is worth 1/6 of what now remains, that is, 125/1296 of the stake. Fermat does not seem to have carried the matter much further, but his correspondence with Pascal shows that his views on the fundamental principles of the subject were accurate: those of Pascal were not altogether correct. Fermat's reputation is quite unique in the history of science. The problems on numbers which he had proposed long defied all efforts to solve them, and many of them yielded only to the skill of Euler. One still remains unsolved. This extraordinary achievement has overshadowed his other work, but in fact it is all of the highest order of excellence, and we can only regret that he thought fit to write so little. _________________________________________________________________ This page is included in a collection of mathematical biographies taken from A Short Account of the History of Mathematics by W. W. Rouse Ball (4th Edition, 1908). Transcribed by D.R. Wilkins (dwilkins(a)maths.tcd.ie) School of Mathematics Trinity College, Dublin

1 0

Re: rant on the morality of confidentiality (fwd)
by Jim Choate 17 Dec '03

17 Dec '03

Forwarded message: > Date: Sat, 10 Jan 1998 16:51:05 -0800 > From: Tim May <tcmay(a)got.net> > Subject: Re: rant on the morality of confidentiality > Doesn't matter how the establishment (whatever that might be) looked on him > or not...you challenged me to name _one_ example, and I named several. Oh, > and it is not true as you later claim that all of my examples "eventually > published" all of their findings. Fermat did not, Gauss did not. Gauss and Fermat both published or shared their works with others contemporaries as demonstrated via their short biographies that I submitted to the list. > My main point has been to refute your notion that any one who elects not to > publish in the open literature cannot be a scientist. I know of many > scientists who could not publish, or chose not to for various reasons. If one doesn't publish (which in the scientific sense means to share publicly ones discoveries, *not* necessarily in open literature - which is a constraint you have never implied before now - changing the rules in the middle of the game are we...and while you go ballistic - when Gauss and Fermat were alive there were no magazines, work was published via demonstrations, books or by letters shared between co-workers) then be so kind as to explain how anyone would find out about the work in the first place, divine intervention? > I mentioned the Manhattan Project scientists. (Choate made some bizarre > claim after this mention that all of the science was known in the 20 and > 30s, and that no actual science was done by MP "engineers" and > "technicians." Might be a surprise to Ulam, Teller, von Neumann, and all > the others who worked in secrecy on the atom bomb, then the hydrogen bomb, > and so on.) What Ulam, Teller, Von Neumann did regarding actualy making the devices; such as the work on explosive lenses; was *engineering or technology* it wasn't science. Science as was extant at the time was quite capable of describing what needed to be done, the question was how to build the damn thing. THAT question is technological not scientific. Furher, at *no* time did I imply that those working on the bomb simply quite working on the theoretical issues that were still unanswered. The reality is, as my original claim, that the process *required both*. However, taking this to the extreme, as you are want to do, of equating them is a disservice to their achievements and the endeavors of science and engineering. Further, if you had done one whit of research on the Manhatten Project you would have found that the *primary* issue for most of the scientist was that the military wouldn't allow them to *share their work*. In many of the letters, depositions, minutes of meetings, etc. there are continous and heated discussion on how the secrecy impacted negatively the process of meeting their goals. Ulam, Teller, Von Neumann, et ali. would be the *first* to refute your claim. > Oh, and what of all the many fine Russian scientists of this century, > nearly all restricted in what they could publish? Because they could not > submit their work to open publication were they not doing science? And very little of what they didn't publish outside of the CCCP made a big difference to what others were doing. As a matter of fact, because of this many of the Russian scientists are reaping the rewards by being passed over for Nobels and other such rewards for sharing their work. A very clear result of this policy in the CCCP was the technological 2nd class that resulted in just about every aspect of Soviet science and engineering outside of some very esoteric and theoretical work. A primary example of *why* and *how* such secrecy *inhibits* rather than promotes science is a study of Russian biological sciences. If you seriously claim that the policy of state secrecy didn't inhibit russian science then be so kind as to explain their clones of the Apple II or the IBM 360, which were truly attrocious in their technology. Just look at the impact on China because of these sorts of policies, it was in the late 1970's before they ever managed to build a TTL equivalent quad-NAND gate, something that the western world had been cranking out since the late 1960's. I got involved in computers and electronics in 1969 *because* those self same 7400 chips were *dumped on the surplus market*. Prey tell how we managed to create a technological millieu that allows 9 year old kids to play with chips for pennies when a whole damn country with a population in the billions can't manage to build and use till nearly 10 years later? > The point being that open publication is only a part of the methodology of > doing science, and a fairly recent one, too. Malarky. If you simply review the history of science (something that is becoming clear you haven't) and study some of these great luminaries works you find that *critical* to all of them was *sharing* their work(s) with others of a similar bent. Their biographies are replete with mentions of letters, meetings, books, etc. they both supplied and received from others. Back to Newton, he graduated in 1665 w/ a BA from Cambridge. Shortly before this he had begun his experiments in light. He published these results in 'Philosophical Transactions' in 1672 and was elected a fellow of the Royal Society the same year because of it. In 1687, at Halleys prompting to abandon his chemical studies (he was an alchemist) and focus on mechanics, he published 'Principia'. This same year is when he became involved in politics which eventualy resulted in his appointment in 1689 to the Convention Parliament of the university. In 1695 he was appointed the Warden of the Mint. In 1727 he was appointed Master of the Mint, which he held until his death. In 1703 he became the president of the Royal Society. That same year he published 'Opticks'. In 1705 he was knighted. He also wrote religous works, two of the best known were 'Observations of the Prophecies of Daniel' and 'Church History'. How in good faith you can claim this doesn't qualify as sharing their work and that such sharing isn't critical to advancement is truly revealing. ____________________________________________________________________ | | | Those who make peaceful revolution impossible will make | | violent revolution inevitable. | | | | John F. Kennedy | | | | | | _____ The Armadillo Group | | ,::////;::-. Austin, Tx. USA | | /:'///// ``::>/|/ http://www.ssz.com/ | | .', |||| `/( e\ | | -====~~mm-'`-```-mm --'- Jim Choate | | ravage(a)ssz.com | | 512-451-7087 | |____________________________________________________________________|

1 0

ENCRYPT XXX PICZ
by kozmo killah 17 Dec '03

17 Dec '03

D3AR S|RZ, H0W D0 | ENCRYPT NUDIE GIFS? W3RD _________________________________________________________ DO YOU YAHOO!? Get your free @yahoo.com address at http://mail.yahoo.com

1 0

Security of Encrypted Magic Folders
by Secret Squirrel 17 Dec '03

17 Dec '03

From: "Alex Woolfson" <abdiel(a)worldnet.att.net> Subject: Security of Encrypted Magic Folders >I just downloaded Encrypted Magic Folders--a program that hides Windows 95 >folders and then encrypts them to prevent a disk utility from revealing >their content. In their help file, they try to answer the question "How >Secure is it?"--and, of course, they say *very*, but I can't tell if this is >so or if they're just blowing smoke. Particularly, their claim that key >size doesn't matter. (My mom taught me size always matters... ) If >someone with a stronger cryptography background than me could take a look at >this and let me know, I would greatly appreciate it. >* How Secure is it? > EMF's encryption offers good protection and excellent speed. It > hasn't been broken yet. It is, as far as we know, exportable. THERE > IS NO BACKDOOR. Should you forget your password there is nothing we > can do to decrypt your encrypted files. How do we know this? > Quite a few people ask us how big EMF's key size is. They've learned > from other encryption programs that the bigger the key the stronger > the encryption. This really doesn't apply to EMF. How do we know this? > We developed our own encryption instead of using a standard because > we wanted EMF to be able to decrypt at the byte level. In this way > we only need to decrypt/encrypt the data your programs require and > not the entire file. How do we know this? > In theory, because we decrypt at the byte level, the biggest key we > could use would be 8 bits - which is a joke. So instead of > decrypting every hunk of data using the same key, as most other > encryption programs do, we developed an algorithm to vary the key > based on the data's location within the file. In this way we get > both high security and high speed. We are trying to patent EMF's > encryption method. How do we know this? And why are they trying to patent a mathematical algorithm? (The fact they can do it is irrelevent. Patenting a mathematical algorithm, much like patenting something like XORing pixels on a screen, is stupid.) And is the fact that they're trying to patent it supposed to make us feel safer? > Having said all that, truth is, most encryption isn't "cracked" by > breaking the algorithm, it's done by guessing the password. Brute > guessing of passwords tends to level the playing field tremendously. Cool. But since we have to disassemble the program to figure out how your program really handles keys...how do we know this? > We actually have an advantage because we aren't an established > standard. Because we're small and relatively obscure chances are no > one will take the effort to write a password guessing program FUD and smokescreen. Security through obscurity. > (which > incidentally would violate copyright and intellectual property laws.) FUD and smokescreen. The fact that creating a password program allegidly violates intellectual property and copyright laws in some country isn't going to keep somebody from writing one. > Even if someone were to go thru all this effort we could easily > change the encryption method for the next update. I doubt it's much effort. For example it can take 3 weeks for a group of programmers to write a copy protection algorithm for their new PC game and about 8 hours for a cracker to break it. Further, if they're patenting this algorithm it will be public. FUD. > If we used an established encryption method like DES or Blowfish then > your files would probably have to be fully decrypted when opened, > would exist on disk as unencrypted while you're using them, and then > would need to be encrypted when closed. This has multiple FUD. Decrypt in relatively small pages and cache in memory. Since they've apparently added an encryption/decryption layer between the filesystem and the userspace libraries to begin with this shouldn't be too hard. Well, then again, considering this is Windows which is probably the worst attempt at an operating system this decade maybe it isn't. >disadvantages. First, if your computer shuts down while you have > "encrypted" files open, then those files would be unencrypted. This Not an issue if the operating system and/or encryption program are/is properly designed. > doesn't happen with EMF as your encrypted files are always encrypted > as stored on disk. The second disadvantage is that it slows things > down tremendously. As an example, let's say you retrieve your email > and your email program needs to add today's message to the end of > your 3MB email file. If we used a standard encryption method > requiring the decryption of the file before use then the entire 3 MB > file would have to be decrypted, your 300 byte message added to the > end and then the entire file encrypted again. With EMF, no > decryption would need to take place, and the only data needing > encryption would be the 300 byte message. MUCH faster. Around > 20,000 times faster in this example! Finally something which might actually be valid. > If you still think you'd like to see us use a standard encryption > method like DES or Blowfish, or have any other suggestions, let us > know and we will consider your input in future updates Unless these people have released source this program should be avoided. The algorithm is unknown, they aren't telling what it is or how it works, it hasn't been submitted for review by cryptographers (at least this list hasn't heard about it), and they aren't releasing source so you can see what's going on. They're hyping security through obscurity as a valid security method, while simultaneously applying for a patent on their security method and saying "Well, if it's cracked we'll just change to another algorithm whenever we get around to releasing the next binary-only distribution. Hope nobody gets your data in the meantime." Further, it is designed for use on an operating system which is notorious for insecurity, where everybody and everything is root (except under NT, where you actually have to make some syscalls to get admin privlidges from an unprivlidged account), where nobody releases source for anything, and where there is no source available for the OS so you can modify it to fix security holes or "features," much less add security enhancements of your own. This entire thing reads like this: "We've developed our own proprietary encryption method which nobody has ever heard of. We don't really know how good it is, but you should believe us when we say it's really, really good. In fact it's so good that we're patenting it just like RSA! Nobody will ever be able to break it because our algorithm isn't in wide use and we aren't releasing source! However if somebody actually does break it your data won't be in the open for long because we'll use some other algorithm which is just as good as the one we came up with originally and got a patent on. Hope you didn't need security in that interim and we hope that when somebody breaks this algorithm they'll tell us rather than taking advantage of all the (for them) plaintext data laying around."

1 0

Redmond to Judge [Expletive Deleted]
by Attila T. Hun 17 Dec '03

17 Dec '03

-----BEGIN PGP SIGNED MESSAGE----- http://www.wired.com/news/news/business/story/9178.html hot off the wire an hour ago! Redmond to Judge - [Expletive Deleted] well, I would expect nothing less than "Fuck You" from Micro$lop --they consider themselves above the law. give Jackson credit for realizing the greater scope of the problem, and for appointing the special master. M$' attitude in and of itself is prima facie evidence of theit market intent --including tossing out the option that OEMs will still be able to but the _original_ version of W95 if they elect not to take IE4. damn white of them boys up there... Analysis: Redmond to Judge - [Expletive Deleted] by Kaitlin Quistgaard and Dan Brekke 4:20pm 15.Dec.97.PST It took two of Microsoft's biggest guns more than 60 minutes to utter a reply to US District Court Judge Thomas Penfield Jackson that most of us sum up in two hard syllables. The second of which is "you." For daring to draw a line last week and forbidding the company to cross for the time being, Jackson was treated to a marathon rebuke from Brad Chase, Microsoft's vice president of Internet marketing, and William Neukom, senior vice president for law and corporate affairs. ... Chase made it clear that neither Jackson nor anyone else would keep Microsoft from readying its planned spring release of Windows 98 - in which Internet Explorer 4.0 and the Windows desktop are inextricably bound. ... Neukom did mention one other alternative that actually merits the name, and one that government the company finds itself at war with might actually recognize as viable: Manufacturers could, he said, install a Netscape browser on their Windows/IE machines. >>> what a fuckin' joke. proves their intent to be a monopoly and fuck the public interest --it's my way, or no way! -----BEGIN PGP SIGNATURE----- Version: 2.6.3i Charset: latin1 Comment: No safety this side of the grave. Never was; never will be iQBVAwUBNJXd/LR8UA6T6u61AQG9bQH/fkE3TKRYOmc+y9RZTsLJYjuISYDYqB47 +G0axtsdcumv7Q09bTYOf8b3K36+ik8/RFdngce6HWXDGrrlmtbd4g== =UuqU -----END PGP SIGNATURE-----

1 0

The Joys of Being Canadian
by Anonymous 17 Dec '03

17 Dec '03

>Phone Company Rep: "What's your Social Security number? >Answer: "I don't have one. I'm Canadian." > >Power Company Rep: "What's your Social Security number? >Answer: "I don't have one. I'm Canadian." > >Cable Company Rep: "What's your Social Security number? >Answer: "I don't have one. I'm Canadian." > >Doctor to Seasoned Citizen: "I can't treat you privately or I'll be barred >from taking Medicare patients for two years." >Answer: "Sure you can. I'm Canadian." Now the question is: When they find out you lied will they care?

3 2

Re: Fw: Jim Bell Sentenced (fwd)
by Jim Choate 17 Dec '03

17 Dec '03

Forwarded message: > Date: Mon, 15 Dec 1997 16:57:22 -0800 > From: Steve Schear <schear(a)lvdi.net> > Subject: Re: Fw: Jim Bell Sentenced (fwd) > > I think both you and Bell are in relatively good agreement on the problem,= > differing mainly on the means of a solution. Well that is the litmus test after all, not the goals but rather the means. > Although, like you I have= > never considerd engaging in acts of violence to right the wrongs in our= > legal structure, I wouldn't say that. I just can't justify them unless under direct physical attack. I am *not* a pacifist. > I also do not believe that the changes you wish can= > reasonably be expected to be achieved through legal and democratic means= > within our lifetimes. I hadn't really entertained the condition that the 'fight' necessarily has to end in my life time. It certainly didn't end in Thomas Jeffersons. I do know that if we don't try we have zero chance of gaining any of them, let alone all of them. And who knows what the future may bring. Personaly I give the US about 20 years before a general political - economic - societal breakdown occurs. I believe that it will be even less violent but just as radical a change as the fall of the CCCP. I further believe that movement will *demand* ethical and reasonably justifiable reference to the respective constitutional documents. I also believe that within about a period of 10 years there will be a significant increase in the number of federal amendments clarifying many of the very issues we discuss today. I believe many things will drive the change. Among them medical technology which will re-grow cloned organs to replace any damaged or diseased ones you may have. I suspect that instead of terra-forming people will clone themselves and geneticaly engineer the embryo to adapt to the relevant environemt (Hint: Dougal Dixon). I believe this technology will fine tune the legal issues we ponder today to a fine edge. I believe the 9th and 10th will be recognized for the defining tests of all federal, state, and individual jurisdictional issues. I believe that as a result of those changes individuals will benefit by being considered equaly with federal and state views. > Almost from the start of our nation, the actions of the Federal branches= > have proven that the Anti-Federalists were right, that the Constitution (as= > accepted) would not prevent their power grab. Wasn't it Article 2, Section= > 18 which was intended to prevent such abuse, and which was easily overcome= > by the SC's liberal interpretation in Maubery vs. Madison? =20 I believe that people will recognize the totality of the current issues as the exact same excesses. People will realize that the camp that demanded specific bills of rights have the right idea. As a result we will get through indipendant state action several amendments. Those movements will be very goal specific and short lived. They will further depend on the Internet for their existance. I believe they will start with individuals in specific points across the US getting in touch and defining a small and specific set of goals (ie Demonstrate constitutionaly that individuals have a right to doctor assisted suicide and that it is an invasion of individual privacy.). As those goals percolate via passive and active processes across the Internet a commen experience will grow. An important question to consider: How long must you hold a sufficient totality of state representation to consider and pass a constitutional amendment? > Little has changed, nor it it likely to, within the system. There's too= > much inertia and entrenched economic and political interest, including the= > electorate's acquiessence to limitations of their liberties in exchange for= > real or imagined protection from harm. I can think of no instance when= > changes, of the magnitude of which you speak, were made during a peaceful= > transition. Can you? No. However, that proves nothing. Simply because something has not happened is no guarantee it won't happen. In all of human history this is the first time that the Internet has existed, photon transportation didn't exist as a verifiable process until just recently, there is now a movement in the dog lovers camp to save clonable samples of favorite pets in the hopes of cloning their best loved pooch. Technology as succesful as ours breeds a technocracy if it doesn't kill us. ____________________________________________________________________ | | | | | We built your fort. We will not have it used against us. | | | | John Wayne - Allegheny Uprising | | | | | | _____ The Armadillo Group | | ,::////;::-. Austin, Tx. USA | | /:'///// ``::>/|/ http://www.ssz.com/ | | .', |||| `/( e\ | | -====~~mm-'`-```-mm --'- Jim Choate | | ravage(a)ssz.com | | 512-451-7087 | |____________________________________________________________________|

1 0

Re: UCENET II and Peter duh Silva
by Charlie Comsec 17 Dec '03

17 Dec '03

-----BEGIN PGP SIGNED MESSAGE----- Information Security <The(a)NSA.sucks> wrote: > : While that's technically true, it's even more true of non-anonymous e-mail > : addresses. Usenet posts are much easier to forge than PGP signatures, and > : it's quite simple to sign up for a throwaway e-mail account under an assumed > : name. It's not very secure from a privacy standpoint, but it's even less > : secure from a "positive ID" POV. > : > : At least with a PGP-signed anonymous post, readers are alerted up front that > : they are reading the work of an author who is withholding his/her identity. > : But if you read a post from "john_smith(a)hotmail.com", is it really someone > : named "John Smith" or not? > > I'm not following this...anyone can generate PGP keys, and digital signatures > are not necessary to indentify an account... Sure, anyone can generate a PGP key. It's almost as easy as generating a throwaway e-mail address. And what does posting from a certain e-mail address or signing one's post with a certain PGP key prove? It proves that the poster KNEW a certain piece of INFORMATION, either an account password or a PGP secret key. It's usually inferred that the person who possesses that information is the person who generated it. Of the two, guessing a PGP secret key is orders of magnitude harder than guessing someone's password, logging on, and impersonating them. In addition, PGP signing is "portable". No matter where I post from, if I sign my post with the same key, you can assume it's me who posted it. It's more difficult to do that with an e-mail address. Let's say that you have a common name like "John Smith" and you post as jsmith(a)someisp.com. Are you saying that's your "identity"? What if Someisp, Inc. suddenly files for bankruptcy and shuts down without warning? Did you lose your identity? You could open a new account as "jsmith" somewhere else and claim you are the same person who previously posted as jsmith(a)someisp.com, but so could anyone else who desired to impersonate you. If you were signing your posts with a PGP key, then all you'd have to do is make a post from your new ISP, sign it with the same key, and your "identity" is "transferred". - --- Finger <comsec(a)nym.alias.net> for PGP public key (Key ID=19BE8B0D) -----BEGIN PGP SIGNATURE----- Version: 2.6.3i Charset: noconv iQEVAwUBNJahmQbp0h8ZvosNAQEqmAf+IG/gtP4flSv/RPP7530NuD5MeMgH8WGo 75E/o+3GkN5Ksl0hL0bdpUhDvqeHnwsdc2xO5j0UEzqIZGKapa1YvJGK0wrUU/FB UrUzcrHkvtXAdJD8GRTaA/Xgzjh2eJGOImzaIHbPOZBa4MPxYm7bEZaroHR2G2IP AkNFbJzBETP9nLmePupRSqmhN8GwC5BLRLjkXLDDXJ/9s04vNoBGUEsv4aA0iRad cdkHjHSs9FfOOTJPPG+GdDA+Z1LuyjnugcoTfYPtsu7PwgWE/tAxOCVPI6sHrhze I1a4KZSVn1AoNd0ii7Mcw4Fp73SUcuZ74+EJovToOyBu++bqZdOYsA== =jF0X -----END PGP SIGNATURE-----

1 0

Re: Radio Free Cypherpunks... (fwd)
by Jim Choate 17 Dec '03

17 Dec '03

Forwarded message: > Date: Mon, 15 Dec 1997 15:49:40 -0800 > From: Steve Schear <schear(a)lvdi.net> > Subject: Re: Radio Free Cypherpunks... (fwd) > > Over a year ago I started a heated thread on the Telecom Regulation list,= > "Basis of FCC jurisdiction," which posited that the Commerce Clause basis= > for FCC authority might not hold for very low power and tens of GHz= > transmissions. My argument, in short, was that if a transmission couldn't= > reasonably be expected to be detectable (using common receiver technology)= > across state lines then the FCC shouldn't have jurisdition. So, are you considering such a broadcast? What I envision is a text-to-speech and/or a digital format. ____________________________________________________________________ | | | | | We built your fort. We will not have it used against us. | | | | John Wayne - Allegheny Uprising | | | | | | _____ The Armadillo Group | | ,::////;::-. Austin, Tx. USA | | /:'///// ``::>/|/ http://www.ssz.com/ | | .', |||| `/( e\ | | -====~~mm-'`-```-mm --'- Jim Choate | | ravage(a)ssz.com | | 512-451-7087 | |____________________________________________________________________|

4 3