HDTenEightyP/NetNews huggingface dataset:
From: zeisset@Informatik.TU-Muenchen.DE (Stephan Zeisset)
Subject: Re: Cypher algorithm question.
Keywords: question, algorithm, encrypt, crypt, decrypt
Originator: zeisset@hphalle5j.informatik.tu-muenchen.de
Organization: TU M"unchen (FRG)
Date: Wed, 29 Jul 1992 10:06:09 GMT


In article <tom.712397505@cluster>, tom@stallion.oz.au (Thomas Essebier) writes:
|> By far not being an expert on cryptology, I would appreciate some 
|> comments on the crypto scheme below. 
|> 
|> Where does it stand in terms of security when compared to transposition 
|> cyphers, DES etc.
|> 
|> My initial thoughts were that other then using a brute force approach,
|> e.g. trying all 2^31 seeds (or so), there is no easy way to deal 
|> with it - but I am probably wrong :-)
|> 
|> I presume that due to its simplicity this sort of crypto approach must
|> be quite well known, its just that in my rather limited explorations of 
|> the field I have not come accros any.
|> 
|> Algorithm:
|> - Create a sequence of random numbers that starts at 'seed' and is known 
|>   to be deterministic and to have a large period. e.g. linear congruential:
|>   X[i+1] = (a*X[i] + c) mod m, choose coefficients as follows 
|>   a = 16807, m = 2,147,483,647 (2^31 - 1), c = 0
|>   #define RANDOM ((unsigned char) (seed = (16807 * seed) % 2147483647))
|>   supposedly has a period of 2^31.
|> 
|> - use the 'key' to choose the first seed, e.g. add up all the bytes or
|>   some such, so that a key >= 4 byte could cover 0-2^31, roughly at least.
|> 
|> - take the the data stream and for each byte 'xor' the LSB of the 'seed'.
|>   A stronger method might be to use 4 byte chunks (assuming seed is 4 bytes)?
|>   The advantage of using xor is that there is that the algorithm is self
|>   reversing. Perhaps it entails some pitfall(s) however?
|> 
|> If anybody could point me to some literature that explains why the above
|> is (un?)reasonably (in?)secure I would be most grateful. Please note that
|> I make no claim to have carefully studied and researched this topic. 
|> I was hoping to avoid all that :-)

The problem with your algorithm is with the know plaintext text.
That means, your opponent knows some of the original plaintext or
makes a good guess of it.
For example, if the plaintext is a letter to someone, you
would expect something like 'Dear Mr ...' or anything alike
in the first few lines of the plaintext.
If I know only 4 Bytes of the plaintext and its position 
(must be divideable by 4) I can easily tell the state of
your random generator at this time (= plaintext word
xor ciphertext word) and decode the following ciphertext.

You could improve your algorithm by:
- Increasing the # of states of your generator,
  e.g. by using an intermediate array:
    r = RANDOM; 
    num = A[index];
    A[index] = r;
    index = r;
    return(num);
- Backcoupling the plaintext into the state of your random
  generator.

Stephan.
From: so@fortran.cs.psu.edu (Nicol C. So)
Newsgroups: sci.crypt
Subject: Re: New record non-networked factorization of difficult number
Date: 24 Jul 92 15:09:17 GMT
Article-I.D.: cs.BrwFFH.CAt
Organization: Penn State Computer Science

In article <26250.Jul2400.28.0492@virtualnews.nyu.edu> brnstnd@nyu.edu (Dan Bernstein) writes:
>Arjen Lenstra and I are pleased to announce the record non-networked
>factorization of a difficult number (no prime factors under 40 digits).
>The number is (2^488 + 1)/257. Its prime factors are p_49 and p_97,
>...
>This computation can be seen as a substantial step towards a practical
>implementation of the general number field sieve (GNFS): it depended on
>character columns and a square root inside the algebraic number field
>rather than explicit generators of the unit group and of prime ideals of
>the field. We are investigating the practical effectiveness of GNFS.

Question: is the technique used here generally applicable to all
composite numbers or is it applicable to composites of special forms?
Newsgroups: sci.crypt
From: jonathan@chpc.utexas.edu (Jonathan Thornburg)
Subject: Re: transposition ciphers
Summary: correction re multiple anagramming
Keywords: cipher transposition multiple anagram broken US civil war
Organization: U of Texas at Austin / Physics Dept / Center for Relativity
Date: Sun, 26 Jul 92 20:33:34 GMT

In article <92207.142318U27239@uicvm.uic.edu> Gerald Strom
<U27239@uicvm.uic.edu> writes [wrote]:
>The following is a little piece I wrote recently about transposition
>ciphers.  As I am far from being an expert in this field, I hope I
>didn't get too much wrong and I would appreciate comments.
> [description and C code deleted]

In article <1992Jul26.074121.15669@chpc.utexas.edu>
jonathan@chpc.utexas.edu (Jonathan Thornburg) [I] writes [replied]:
>Shouldn't you also point out that any transposition cipher can be
>broken by multiple anagramming?  Kahn "The Codebreakers" discusses
>this and gives a couple of examples of broken transposition ciphers,
>I believe dating back to the US civil war and the 1884 (?) US
>presidential election.

Oops, I must have missed a refresh cycle on my brain (this is what
comes of posting at 230am).  My statement was too strong.  I should
have said:
"Shouldn't you also point out that unless special precautions are
 taken to the contrary, transposition ciphers can be broken by
 multiple anagramming?"

- Jonathan Thornburg
  <jonathan@einstein.ph.utexas.edu> or <jonathan@hermes.chpc.utexas.edu>
  University of Texas at Austin / Physics Dept / Center for Relativity
  and (for a few more months) U of British Columbia / {Astronomy,Physics}
From: hoppie@nemesis.East.Sun.COM (Tom Hopkins - Sun ECOPS IR)
Newsgroups: sci.crypt
Subject: Re: passwd security check
Date: 30 Jul 1992 17:24:41 GMT
Organization: Sun Microsystems, Inc.
Distribution: world
Reply-To: hoppie@nemesis.East.Sun.COM
NNTP-Posting-Host: nemesis.east.sun.com


In article <5GL@solbourne.com>, imp@solbourne.com (Warner Losh) writes:
>I thought that the 01010101 was a series of bit values, rather than
>hex values.  Since they are hex values, they are indeed quite hard to
>type as characters at a Password: prompt.  Sorry for any confusion
>that my previous post may have caused.

Actually, I found this particular series quite easy to input at a
Password: prompt.  01 hex is Control-A.

-Tom Hopkins <hoppie@turbo.East.Sun.COM>
I doubt I speak for anyone in this organization, including myself.
From: paul@kuhub.cc.ukans.edu
Newsgroups: sci.crypt
Subject: NIST stumbles on proposal for public-key encryption
Date: 27 Jul 92 13:04:48 CDT
Organization: University of Kansas Academic Computing Services

The industry newspaper/magazine "Network World" has an excellent
article about the NIST's Digital Signature Standard (DSS) and the
controversy surrounding it, as opposed to international acceptance of
RSA for both signatures and encryption.

See "Network World", 7/27/92, p. 1, "NIST stumbles on proposal for
public key encryption".
From: mrr@scss3.cl.msu.edu (Mark Riordan)
Newsgroups: sci.crypt
Subject: Re: "random generator" passwords (was: Re: Keeping track of a lot of passwords)
Date: 26 Jul 92 18:56:23 GMT
Organization: Michigan State University
X-Newsreader: Tin 1.1 PL3

jonathan@chpc.utexas.edu (Jonathan Thornburg) writes:
: Using a random number generator (RNG) to generate passwords is
: almost always a very bad idea -- it yields *highly* *insecure*
: passwords.  There are two reasons for this:
: [...] 
: Remembering multiple cryptographically-independent-and-high-entropy
: passwords is a hard problem, but using a "small rng" to generate them
: is not the solution.

Yes, the classic 2-line PRNG is probably not so good for generating
passwords.  However, a cryptographically strong function, such as 
DES or MD5, probably would be suitable.  In fact, I wouldn't be
surprised if crypto-based pseudo-random number generators turned
in strong performances on most or all general-purpose PRNG tests.  
They'd be somewhat slower than most of the competition, though,
and not easy to program into a hand-held calculator.

The obvious way of making a PRNG generator from a crypto function,
of course, is:

  random[0] = function(key)
  random[i] = function(random[i-1])

with suitable post-processing on random[i] to turn it into an integer,
floating point, or what-have-you.

Mark R.
Newsgroups: sci.crypt,comp.security.misc
From: coar@Nephi.Enet.DEC.Com (Rodent of Unusual Size)
Subject: Re: Crypt should be based on MD5 (was: the Crypt 16 discussion)
Summary: Can limit exposure
Keywords: password, expiration, goodness/evility
Organisation: Employed by (*NOT* speaker for) DEC, Boxborough, MA, U.S.A.
Organization: Digital Equipment Corp.
Date: Thu, 23 Jul 1992 13:45:20 GMT


    Well, having a password expiration can limit exposure under some
    circumstances.  If passwords are fairly well chosen (none of this 91Jan,
    91Feb, 91Mar stuff), and one should happen to be revealed accidentally
    (NOT deduced or decrypted), the account is exposed only until the next
    time the password must be changed.  The actual window of exposure can be
    anywhere from 0 to T (where T is the password lifetime), depending upon
    when the password was disclosed.

    I'm not sure of the value of this, but it seemed reasonable to bring it
    up.

    Of course, if the lifetime is too long, this window grows.  If it is too
    short, the user will circumvent it by writing the password down in a
    convenient place or otherwise not safeguard it appropriately.  Based upon
    experience, I feel a couple of months is a reasonable value for most
    users.  Your kilometreage may vary..

    Practical security is a balancing act, sailing between the Scylla of
    exposure and the Charybdis of user convenience.

    #ken    :-)}	Jeratol the Chaotic

Coar@Nephi.Enet.DEC.Com	 | All opinions herein contained, stated or implied,
Coar@DECUS.Org		 | are solely those of the author.  And he's fullovem.
Coar@Eisner.DECUS.Org	 | `... it was mine art, ... that made gape the pine 
Massachusetts, USA       | and let thee out.'  - Prospero (_The Tempest_)
From: kingj@hpcc01.corp.hp.com (John C. King)
Date: Thu, 23 Jul 1992 15:54:30 GMT
Subject: Export Restrictions lessening?
Organization: the HP Corporate notes server
Newsgroups: sci.crypt

*-*20 US eases export controls on encryption systems (DB 23/7)

    The export of defenses against hackers and viruses is to
    be made easier for US software companies.  Brent
    Scowcroft, White House National Security Adviser, said
    that the government will "expeditiously" transfer some
    encryption software to the Commerce Department's less
    restrictive Commodity Control List.
    Wall Street Journal/Europe. English. 1992-07-23. Size: 1 c
From: phr@soda.berkeley.edu (Paul Rubin)
Newsgroups: sci.crypt
Subject: Re: RSA Public Key Generations.
Date: 29 Jul 92 09:39:38
Organization: CSUA/UCB
NNTP-Posting-Host: soda.berkeley.edu
In-reply-to: avalon@coombs.anu.edu.au's message of 29 Jul 92 08:46:06 GMT

    Hi, I've been looking at implementing RSA encrpytion and have found that
    generating the initial keys is a somewhat tricky.  The only algorithm
    I have found for generation the public key is:

    N = x*y
    p*s mod (x-1)(y-1) = 1

    and solve for p. :(

    Is there an easy way to solve this problem ?

It's straightforward to do this with Euclid's algorithm.
See for example Knuth vol. 2.  (Look in the index under Euclid). 
Most other algorithm books or number theory books should explain
this algorithm also.
Newsgroups: sci.crypt
From: weaver@sfc.sony.com (Eric Weaver)
Subject: RSA keys
Organization: Sony Advanced Video Technology Center
Date: Thu, 30 Jul 1992 21:37:09 GMT


Summarized for those who haven't a Knuth Vol. II:

 Pick two primes, P and Q, which are NOT one greater than a multiple of 3
  (e.g. 37 won't do).  Probabilistic prime tests are good for this.

 Take a frame of bits F, no shorter than 1/3 the length of PQ (the
public, encryption key), and less than PQ.  

 Encrypt:  F[enc] = F^3 mod PQ.

 Let D (private, decryption key) = [(P-1)(Q-1)/6]+1

 Decrypt: F = F[enc]^D mod PQ.


 P and Q should be of approx. 25% difference in length, and of at
least 450 bits total.  1000 bits or more, if you can afford it, would
be best.

 Decryption is pretty expensive, obviously, so this technique is
commonly used only to exchange key and digest info.

Question for cognoscenti: How hard is it REALLY to guess or search D
from PQ?
-- 
Eric Weaver  Sony AVTC  677 River Oaks Pkwy, MS 35  SJ CA 95134  408 944-4904
& Eng. Asst., KFJC 89.7 -  Foothill College, Los Altos Hills, CA 94022
Newsgroups: sci.crypt
From: jac54@cas.org ()
Subject: Re: transposition ciphers
Keywords: cipher transposition multiple anagram broken US civil war
Organization: Chemical Abstracts Service, Columbus, Ohio
Date: Mon, 27 Jul 1992 11:13:22 GMT

In article <1992Jul26.074121.15669@chpc.utexas.edu> jonathan@chpc.utexas.edu (Jonathan Thornburg) writes:
>In article <92207.142318U27239@uicvm.uic.edu> Gerald Strom
><U27239@uicvm.uic.edu> writes:
>>The following is a little piece I wrote recently about transposition
>>ciphers.  As I am far from being an expert in this field, I hope I
>>didn't get too much wrong and I would appreciate comments.
>> [description and C code deleted]
>
>Shouldn't you also point out that any transposition cipher can be
>broken by multiple anagramming?  Kahn "The Codebreakers" discusses
>this and gives a couple of examples of broken transposition ciphers,
>I believe dating back to the US civil war and the 1884 (?) US
>presidential election.
>
	Doesn't this only work with a route and/or block transpositions?
	When a transposition using a randomized mapping (transposition
	sites randomly assigned) it becomes much more difficult,
	especially if your map is a one-time pad.  Incidentally, there
	are only about 40 systematic routes through a 5x5 transposition
	block.  I tried working them out once, it's very character-
	building.

	Alec Chambers.
From: phr@soda.berkeley.edu (Paul Rubin)
Newsgroups: sci.crypt
Subject: Re: Lucifer revisited
Date: 28 Jul 92 23:04:16
Organization: CSUA/UCB
NNTP-Posting-Host: soda.berkeley.edu
In-reply-to: erc@unislc.uucp's message of 28 Jul 92 21:37:45 GMT

I heard somewhere that Lucifer was vulnerable to key reestimation attacks.
From: tf@cl.cam.ac.uk (Thomas Forster)
Newsgroups: sci.logic
Subject: unexpected examination
Date: 28 Jul 92 14:00:00 GMT
Reply-To: tf@cl.cam.ac.uk (Thomas Forster)
Distribution: sci.logic
Organization: U of Cambridge Comp Lab, UK


I need a bibliography on the unexpected hanging/examination
since i wish to cover it in a course of lectures I am writing.
The bibliography i have collected is complete up to about 1967.
If anyone knows later published material, I would be most grateful
if they could email me at tf@pmms.cam.ac.uk with the details. 

     Thomas Forster
From: hbe@sonia.math.ucla.edu (H. Enderton)
Newsgroups: sci.logic
Subject: Re: quantifier elimination
Date: 24 Jul 92 22:13:57 GMT
Organization: UCLA Mathematics Department

In article <1992Jul24.151022.7360@cs.albany.edu> subu@cs.albany.edu
(Mahadevan Subramaniam) writes:
> Can somebody point out to me references for quantifier elimination 
> over the theory of real numbers. 

This is in Shoenfield's book, "Mathematical Logic," page 87.
Shoenfield gives a model-theoretic proof that the theory of the
real ordered field admits elimination of quantifiers.  The
result is due to Tarski (about 1939, but not published until
after the war).  There is more recent work on upper and lower
bounds on the complexity of implementation of the decision 
procedure one gets from all this.

--Herb Enderton    (hbe@math.ucla.edu)
Newsgroups: sci.logic
From: boshuck@triples.math.mcgill.ca (William Boshuck)
Subject: Re: Equivalence of Strong completeness and categoricity
Organization: Dept Of Mathematics and Statistics
Date: Tue, 28 Jul 92 02:52:11 GMT

In article <1992Jul22.205827.16651@cenatls.cena.dgac.fr> alliot@cenatls.cena.dgac.fr (Jean-Marc Alliot) writes:
>
>Consistency: A system is consistent if, for any wff F, we
>can not have at the same time (F is a theorem) and (not F is a
>theorem). 
>
>Categoricity: a system is categoric if, for any wff F, we have either
>(F is theorem) or (not F is a theorem).
>
>Strong completeness: a system based on a set S of axioms is strongly
>complete if for any wff F, we have either (F is a theorem) or (F added
>to S is an inconsistent system).
>
>
>Now the questions:
>
>1) It seems quite clear that in any system which is a superset of
>propositional calculus Categoricity and Strong completeness are
>equivalent. However a short and clear demonstration would be very much
>welcome.
>
>2) Does the property hold in the general case (I especially think of
>intuitionist logic) ?

The proof which answers question 1) depends on something
called the deduction theorem which, in turn gives an answer to
the second question. The deduction theorem says that for a
theory T and formulas F,G, that the following inferences (both
top to bottom and bottom to top) are valid

                T,F |- G
              ------------
              T |- F ==> G   .	

(I am using |- to denote provability in whatever logic is
under consideration) In some treatments of logic, this is
virtually the definition of implication (perhaps rightly so).
In particular, this rule is valid in intuitionistic, and modal
logics (at least in the more common ones like S4).

If T is a theory in a logic which admits the above rule for
implication then we can say the following. First, categoricity
implies strong completeness: Suppose T is categorical. If T |-
F then that's it. Otherwise, T |- ~F in which case T,F |- F &
~F so T adjoin F is an inconsistent theory. Now, strong
completeness implies categoricity: Again, if F is a theorem
then you're done.  Otherwise, T adjoin F is an inconsistent
theory; that is, T,F |- (false). By the above rule we get
T |- F ==> (false), that is, T |- ~F. 

I hope this has been helpful.

WHB


Newsgroups: sci.logic
From: gar@cltr.uq.oz.au (Greg Restall)
Subject: Re: Equivalence of Strong completeness and categoricity
Organization: Centre for Language Teaching and Research, Uni of Queensland, AUSTRALIA.
	<1992Jul28.025048.6503@thunder.mcrcim.mcgill.edu>
Date: Tue, 28 Jul 1992 06:09:32 GMT

boshuck@triples.math.mcgill.ca (William Boshuck) writes:

* The proof which answers question 1) depends on something
* called the deduction theorem which, in turn gives an answer to
* the second question. The deduction theorem says that for a
* theory T and formulas F,G, that the following inferences (both
* top to bottom and bottom to top) are valid
*
*                T,F |- G
*              ------------
*              T |- F ==> G   .	
*
* (I am using |- to denote provability in whatever logic is
* under consideration) In some treatments of logic, this is
* virtually the definition of implication (perhaps rightly so).
* In particular, this rule is valid in intuitionistic, and modal
* logics (at least in the more common ones like S4).

Pretty good so far...

* If T is a theory in a logic which admits the above rule for
* implication then we can say the following. First, categoricity
* implies strong completeness: Suppose T is categorical. If T |-
* F then that's it. Otherwise, T |- ~F in which case T,F |- F &
* ~F so T adjoin F is an inconsistent theory. 

But not here.  

It's not that it's in *error*, but just that it's not
so general.  There are plenty of good logics (like R,
R-W, Linear Logic, and so on), that satisfy modus ponens
and the deduction theorem (in the way you describe), 
but that don't validate the move:

	 A |- C
	--------  (Weakening; or K)
	A,B |- C

which you need (in some form) to get from T |- ~F to 
T,F |- F & ~F.

The reason you might want to get rid of the offending
principle is to invalidate the offensive

	 |- C
	-------
	|- B->C

which is invalid in all of the systems mentioned above,
and frankly, which *ought* to be invalid, on many sensible
readings of `->'.

Relevantly yours,

Greg Restall


--
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - 
Greg Restall        Philosophy Department, University of Queensland.   
gar@cltr.uq.oz.au   Queensland, 4072.  Australia.		         
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - 
The day logic stops being fun is the day it ceases to be my profession.
							   -- Bob Meyer
From: unregistered@newcastle.ac.uk (Tony Dale)
Newsgroups: sci.logic
Subject: inconsistent proofs
Date: 21 Jul 92 17:28:43 GMT
Organization: Newcastle University, U.K.


One of Wette's papers was published in the reputable belgian journal 
'Logique et Analyse' around 1976, together with a disclaimer from the 
editor who prefaced the paper with his reasons for publishing the paper 
which were to counter Wette's claims that the academic community were 
dekiberately preventing his papers from being published.  I also remember 
Wette behaving badly (by academic conference standards!) at a conference 
at the University of Bristol in 1974.  He kept heckling a rather frail 
Paul Bernays during what must have been one of the last conference papers 
that Bernays ever gave.
As for the International Logic Review I know that the names that appeared 
on the cover as its distiguished editorial board did not coincide with its 
real editorial board which I suspect consisted of Spisani alone.  I know 
that at least one of those individuals names tried to remove their names 
from the cover.  In addition I once entered a paper to the said journal in 
my more naive days.  I heared nothing re the paper but I did have a letter 
from Spisani saying that he had always been interested in my work and that 
he was willing to publish any papers I had and distribute them to 
libraries throughout the world if I sent him a certain sum of money!.  The 
journal continued to arrive gratis for many years but seems to have 
stopped.  It is no loss.
Tony Dale.

Tony Dale,
Computer Laboratory,
University of Newcastle
U.K.
From: subu@cs.albany.edu (Mahadevan Subramaniam)
Newsgroups: sci.logic
Subject: quantifier elimination
Date: 24 Jul 92 15:10:22 GMT
Organization: The University at Albany, Comp. Sci. Dept.
Originator: subu@hartmanis.albany.edu

Hello,
 Can somebody point out to me references for quantifier elimination 
 over the theory of real numbers. 
  Thanks a lot in anticipation.
From: alliot@cenatls.cena.dgac.fr (Jean-Marc Alliot)
Newsgroups: sci.logic
Subject: Equivalence of Strong completeness and categoricity
Date: 22 Jul 92 20:58:27 GMT
Organization: Centre d'Etudes de la Navigation Aerienne, Toulouse, France


This question is perhaps trivial but...

I am first going to give the definition I am using, since many people
use the same words for different things: 

Consistency: A system is consistent if, for any wff F, we
can not have at the same time (F is a theorem) and (not F is a
theorem). 

Categoricity: a system is categoric if, for any wff F, we have either
(F is theorem) or (not F is a theorem).

Strong completeness: a system based on a set S of axioms is strongly
complete if for any wff F, we have either (F is a theorem) or (F added
to S is an inconsistent system).


Now the questions:

1) It seems quite clear that in any system which is a superset of
propositional calculus Categoricity and Strong completeness are
equivalent. However a short and clear demonstration would be very much
welcome.

2) Does the property hold in the general case (I especially think of
intuitionist logic) ?

If the question is too trivial, a reference to a book giving the
answers would be also welcome.
From: fabio@inagaki.nuie.nagoya-u.ac.jp (Fabio Casablanca)
Newsgroups: sci.logic
Subject: Kleene 3-valued logic
Date: 18 Jul 92 05:48:35 GMT
Distribution: sci.logic
Organization: Inagaki Lab., Dept. of Info. Eng., Nagoya Univ.


I am interested in model theory connected to Kleene 3-valued logic.

I am also interested to applications of this logic to logic programming 
and computer science.

Any pointer will be greatly appreciated.

fabio
--
Fabio CASABLANCA
    Inagaki Laboratory-Information Engineering Dept.-Nagoya University
    E-MAIL:fabio@mars.inagaki.nuie.nagoya-u.ac.jp
    FAX NUMBER:(052)782-8260
  
        
Newsgroups: sci.logic