Re: Optimal solution
Best means best for some specific objective. Optimal means the same thing as best. Depends on what you want to do. There are countless examples of problems for which different algorithms scale differently by problem size, e.g. for N=10, Algorithm A is the fastest solution, but for N=1000, Algorithm B is much faster. I guess you mean like seives like NFS and QS. There are also lots of examples of problems for which one algorithm has an asymptotic lower bound that's the lowest known (or some other type of best), Is n't it the big Oh-upper bound that determines if it is best-since we always consider the worst case scenario. yes,i remember that algorithm of primality in P. thank you for answering. Regards Data. __ Do you Yahoo!? Faith Hill - Exclusive Performances, Videos More http://faith.yahoo.com
Optimal solution
hi, In the case of algorithms is the best algorithm always the best solution to the problem,be the algorithm with a constant run time or randomised algorithm. i.e is the best solution always the optimal solution for a problem. how can we argue -either way? Thank U. Regards Data. __ Do you Yahoo!? Faith Hill - Exclusive Performances, Videos More http://faith.yahoo.com
Doubt on O notation.
hi, I have problem understanding time complexity for the following problem I need to check if two strings are equal let string one s1=aaabbb and string two s2=aaabbb We place it on a single tape turing machine aaabbb aaabbb the book says it takes roughly 2n steps to match corresponding alphabet of s1 with s2,that much i understand. therefore the whole computation takes O(n^2) time. how is that,should n't be O(2n) the same if placed on a two tape turing machine is as shown tape 1: aaabbb tape2 : aaabbb and they are compared simultaneouly and have a time complexity of O(n) which is understandable. How ever i didnt get how we get O(n^2) in the previous case. In automata the number of sentential forms cannot exceed M=|p|+ |p^2| + ...+ |p|^(2|w|) where w is the length of the input string.p is the finite set of productions. I dont see how it is applicable here. pls help.Thank you. Regards Data. __ Do You Yahoo!? HotJobs - Search Thousands of New Jobs http://www.hotjobs.com
Re: [CI] Re: Turing thesis(Incompleteness theorom)
hi, thank you Mr. Jim,one more query, regarding Godel's incompleteness theorom. with reference to http://www.miskatonic.org/godel.html Gödel asks for the program and the circuit design of the UTM. The program may be complicated, but it can only be finitely long. Call the program P(UTM) for Program of the Universal Truth Machine. we know that there are unprovable and provable statements and there is no way to distinguish all solvabe problems from unsolvable ones as you said below. Also have can we distinguish between provable and unprovable statements. That is an unsolvable problem if you are looking for a general approach to -any- statement, that -is- Godel's. In godel's theorom,above mentioned,it says circuit design and programme must be finitely long. Is that necessary?we can't say for sure,right?Isn't it an unprovable statement which is made or more likely an assumption. if we say other wise,why has the programme to be finite? Thank you very much. Regards Data. __ Do You Yahoo!? HotJobs - Search Thousands of New Jobs http://www.hotjobs.com
Turing thesis
hi,
Here is an example illustrating turing thesis
{ Suppose we make a conjecture that a turing machine
is equal to the power of a typical digital
computer?how can we defend or refute sucha hypotheis?
to defend it we could take an increasingly more
difficult and show that they are solvable by some
turing machine...still while every sucess in this
direction will strengthen our conviction of the
truth of the hypothesis,it will not lead to a proof.
The difficulty lies in the fact that we dont exactly
know what is meant exactly by a typical digital
computer and we have no means of making a precise
defenition)
Is the defenition not possible because of the
incompleteness theorom?
why exactly is it undefinable?
Also have can we distinguish between provable and
unprovable statements.
Regards Data.
__
Do You Yahoo!?
HotJobs - Search Thousands of New Jobs
http://www.hotjobs.com
Re:Atmospheric noise fair coin flipping
hi, thanx a lot,there is one more doubt. The rules of physics are those that don't change from time to time, or place to place i tend to disagree with this. the hierarchy goes like okay let us say that two bodies with mass attract each other. it was an observation of a physical body,then we make a mathametical model of the phenomenon. Based on the mathametical model we make laws of physics. The mathametical observations rely on the parameters that are taken to make the mathametical model. if the parameters changes,the mathametical model will have to be changed and new laws have to be brought. with what certainy can we say that additional parameters will not be added or removed and that the laws of physics will stay true for ever? If a new parameter ever gets added may be two bodies with mass may repell each other. can we say that these parameters will never change? Regards Data. --- Optimizzin Al-gorithym [EMAIL PROTECTED] wrote: At 05:45 AM 7/14/02 -0700, gfgs pedo wrote: it is said that atmospheric noise is random but how can we say for sure. Physics, chaos, the growth of initial uncertainty as systems evolve, energy/time required to make measurements to arbitrary precision. what if the parameters giverning atmospheric noise vary frm time 2 time. The rules of physics are those that don't change from time to time, or place to place. Certainly the e.g., wind speed does. so can we say atmospheric noise is random or a coin flipping is random-only because it passes die hard test or other randomness tests-which is an indicator of randomness with the current defenition of parameters in determing randomness? No, since 'anything through a whitener passes' these tests. The integers (0, 1, 2..) fed into DES will pass. (Equivalently) A low-entropy source fed into a hash will pass. [Historical note: this is why Intel should make its raw RNG data available in chips with whitened-output RNG functions] To have a true RNG, You *must* have a physical understanding of the source of entropy whence you distill the pure bits (whether or not you feed it into a whitener after distillation). Precisely because a 'black box' may be a deterministic (if you know the secret) PRNG. By 'distill' I mean reduce N bits to M, N M, in such a way as to increase the entropy of the resultant M bits. is there truly random or that we can say with certain degre of confidence that they are nearly random as all current evidence poits so. 'Random' should be taken to mean 'ignorant of'. It suffices that we (and our adversary) are ignorant of the detailed conditions inside a noise diode, unstable atomic nucleus, atmospheric (or FM radio) noise receiver, etc. Philosophical discussions about 'true randomness' (Is there a deeper/smaller level of description in which apparently-random events are based or emerge from?) are beyond the scope of this rant. __ Do You Yahoo!? Yahoo! Autos - Get free new car price quotes http://autos.yahoo.com
RE: Finding encrytion algorithm
hi, I get the idea,thanx. Regards Data. can u pls explain how they have statistical signatures,pls- may be using SPN's, i have tried ANSI X9.17 key generation with GOST-it did have a negligably small skew-it makes me wonder what statistical signature they have.The negligable skew is a weakness but not high enough to compramise the security of the key used from the ANSI x9.17 key gen method. pls explain. thank u veru much. You're on the right track. Take several encryption algorithms of your choice, then use a fixed IV, and the same sets of keys, and encrypt blocks of 0's. For each algorithm, compute several sets of staticstics (a la NIST or DIEHARD). With 100 blocks of 10 Megabytes (100 different keys) you should see some interesting differences. Remember, your question originally was how can you tell which algorithm, not how do you find the key. Let us know what you find out :-) --yes :) Patience, persistence, truth, Dr. mike __ Do You Yahoo!? Yahoo! Autos - Get free new car price quotes http://autos.yahoo.com
Atmospheric noise fair coin flipping
hi, Does a fair coin exist in real world? Like as according to Allan Turing-an event is defined by set of certain parameters governing the event at that instant. by redoing the same experiment-do we always have the same set of parameters that previously defined the coin. it is said that atmospheric noise is random but how can we say for sure. what if the parameters giverning atmospheric noise vary frm time 2 time. may be at a later stage an additional parameter may govern atmospheric noise or may be a parameter may be removed,we cant say that for sure. like the earth moon attract each other,no 1 knows why,it is a physical observation based on it we make a matahmetical model,what if one day-2 bodies with mass start repelling each other? then an extra parameter would govern it we will have 2 change the mathametical mode considering this additional parameter. so can we say atmospheric noise is random or a coin flipping is random-only because it passes die hard test or other randomness tests-which is an indicator of randomness with the current defenition of parameters in determing randomness? is there truly random or that we can say with certain degre of confidence that they are nearly random as all current evidence poits so. Regards Data. --- Jim Choate [EMAIL PROTECTED] wrote: Perhaps a simpler example. Let's look at a 'fair' coin and what that means in the real world. A normal coin (or any nDx for that matter [1]) for short sequences is random. In other words if you record a game sequence and then replay the game the die sequence won't have any statistical correlation. Knowing what happened last time won't help you this time, the 'window of opportunity' with respect to statistical bias isn't large enough, so the game is 'fair'. But!, if you throw that coin once a second for a billion years you will find that -no- coin is really -fair-. This goes back to k-sequences and Knuth. Go back and then start throwing it again, and if your sequence is long enough you can use this known bias from the first experiment to increase your percentage of 'hits' in the second sequence. In other words you can now prove experimentaly the coin isn't fair and what that bias is. This is related to 'Hypothesis Testing'. It's rather strange, but I happen to be rereading a book, The Mathematical Sciences: A Collection of Essays (LoC# 69-12750) put out by some group called COSRIMS in about 1969. I remember the book because somebody gave it to me (I was about 9 or 10 at the time) to read, and it has an insane bright yellow cover. I recently came across it again in a used bookstore for $10 so I bought it. It's basically a bunch of chapters on various issues of math research with the intent of focusing high school and undergrads to pursue mathematical careers by giving examples of what you might be working on. The chapter Statistical Inference (by J. Kiefer) uses an example of a coin and a 3-run sequence to determine the actual bias of the coin (the example is very simple, the coin is very biased). You should be able to still find the book in public libraries and college libraries. I'm sure more modern texts on hypothesis testing will be just as relevant. The vast majority of RNG's that we use are really PRNG's, we just don't collect enough data on them to be able to demonstrate that. Or the sequence of interest is so short we dont' care. [1] A coin is a 1D2, two coins would be 2D2, for example. Who said wargaming was worthless ;) On Sat, 13 Jul 2002, Mike Rosing wrote: On Sat, 13 Jul 2002, gfgs pedo wrote: can u pls explain how they have statistical signatures,pls- may be using SPN's, i have tried ANSI X9.17 key generation with GOST-it did have a negligably small skew-it makes me wonder what statistical signature they have.The negligable skew is a weakness but not high enough to compramise the security of the key used from the ANSI x9.17 key gen method. pls explain. thank u veru much. You're on the right track. Take several encryption algorithms of your choice, then use a fixed IV, and the same sets of keys, and encrypt blocks of 0's. For each algorithm, compute several sets of staticstics (a la NIST or DIEHARD). With 100 blocks of 10 Megabytes (100 different keys) you should see some interesting differences. Remember, your question originally was how can you tell which algorithm, not how do you find the key. Let us know what you find out :-) Patience, persistence, truth, Dr. mike -- When I die, I would like to be born again as me. Hugh Hefner [EMAIL PROTECTED] www.ssz.com [EMAIL PROTECTED] www.open-forge.org
Re: Finding encrytion algorithm
hi, thanx Mr Jim. Data. __ Do You Yahoo!? Yahoo! Autos - Get free new car price quotes http://autos.yahoo.com
Finding encrytion algorithm
i meant cryptanalyst-hope i spelled that rite :-) Data. __ Do You Yahoo!? Sign up for SBC Yahoo! Dial - First Month Free http://sbc.yahoo.com
Finding encrytion algorithm
hi, suppose a cryptanalysis only has encrypted data-how is going 2 know which is the encrytion algorithm used 2 encrypt the data ,so that he can effeciently cryptanalyse if 1:he has large amount of cipher text only 2:has large amount of plain text and corresponding cipher text. There r so many encryption algorithms,how does he know which algorithm was used? Regards Data. __ Do You Yahoo!? Sign up for SBC Yahoo! Dial - First Month Free http://sbc.yahoo.com
Man in middle attack
hi, The only thing that might, as far as I can see, succeed (with a high probability) would be for everyone to hash the *next* half - meaning that, together with half 2 of message N, there will be the hash of half one of message N + 1. However, I don't see how this would be possible for an interactive communication... As far as i can extend the previous attack,i.e faking 1 packet for interlock protocol in the above 1 you propose,extending the same attack it only takes Mallory one and a half faked packets to launch a succefull attack on the above proposal. let A=Alice M=Mallory B=Bob let 1:1 indicate 1 st packet ,1st half 1:2 indicate 1 st packet , 2nd half 2:1 indicate 2 nd packet, 1st half 2:2 indicate 2nd packet , 2nd half and so on so we are now have 1:2 and 2:1 as one complete message and so on No: A MB 1A-1:1 M-1:1 2M-1:1 B-1:1 3A-1:2 M-1:2 4M-1:2 B-1:2 5A-2:1 M-2:1 6M-2:1 B-2:1 7A-2:2 ** The blank spaces corresponding to each row indicates that it is a sender and the other 2 are receivers. Once Mallory receives A-2:2 ,he has 2 full packets in hand and has faked 1 and a half packets(Step 7) indicates that it is now the earler packet Bob receives of Alice after Mallory's manupilation. I hope that table will give some clarity. now he can send Bob the original message of Alice. So I think the above suggested protocol will not work. Mallory can still get away with his scheme Regards Data. --- Marcel Popescu [EMAIL PROTECTED] wrote: From: gfgs pedo [EMAIL PROTECTED] One solution suggested against the man in the middle attack is using the interlock protocol This is the one I vaguely recalled, thank you. All mallory would have to do is send the half of the (n th) packet when he receives the half of (n+1)th packet since the 1 st packet was faked by mallory. Interesting attack... assuming that a one-block delay doesn't look suspicious. What if every message except the very first one has a hash of the previously received message? A - (M -) B: half 1 of message A1 B - (M -) A: half 1 of message B1 | hash (half 1 of message A1) A - (M -) B: half 2 of message A1 | hash (half 1 of message B1) B - (M -) A: half 2 of message B1 | hash (half 2 of message A1) A - (M -) B: half 1 of message A2 | hash (half 2 of message B1) ... and so on Nah... won't work; since M captures A1 and B1, he can compute the hashes for both the initial bogus message and the (delayed) genuine ones. Same if they try hasing all the previous messages. What if they send the hash of the *other* half? (The program splitting the messages already has the full ones.) A - (M -) B: half 1 of message A1 | hash (half 2 of message A1) B - (M -) A: half 1 of message B1 | hash (half 2 of message B1) A - (M -) B: half 2 of message A1 | hash (half 1 of message A1) B - (M -) A: half 2 of message B1 | hash (half 1 of message B1) ... and so on Nope, no good... M fakes the first message in both direction, and then he always has a good one, so he can compute the hashes. The only thing that might, as far as I can see, succeed (with a high probability) would be for everyone to hash the *next* half - meaning that, together with half 2 of message N, there will be the hash of half one of message N + 1. However, I don't see how this would be possible for an interactive communication... Thanks, Mark __ Do You Yahoo!? Sign up for SBC Yahoo! Dial - First Month Free http://sbc.yahoo.com
Re: Diffie-Hellman and MITM
hi, Thanx Mark, I was also wondering on the line of hash functions too,me 2 dont see how it works securely. Nor does the interlock protocol look secure to me. Regards Data. --- Marcel Popescu [EMAIL PROTECTED] wrote: From: gfgs pedo [EMAIL PROTECTED] One solution suggested against the man in the middle attack is using the interlock protocol This is the one I vaguely recalled, thank you. All mallory would have to do is send the half of the (n th) packet when he receives the half of (n+1)th packet since the 1 st packet was faked by mallory. Interesting attack... assuming that a one-block delay doesn't look suspicious. What if every message except the very first one has a hash of the previously received message? A - (M -) B: half 1 of message A1 B - (M -) A: half 1 of message B1 | hash (half 1 of message A1) A - (M -) B: half 2 of message A1 | hash (half 1 of message B1) B - (M -) A: half 2 of message B1 | hash (half 2 of message A1) A - (M -) B: half 1 of message A2 | hash (half 2 of message B1) ... and so on Nah... won't work; since M captures A1 and B1, he can compute the hashes for both the initial bogus message and the (delayed) genuine ones. Same if they try hasing all the previous messages. What if they send the hash of the *other* half? (The program splitting the messages already has the full ones.) A - (M -) B: half 1 of message A1 | hash (half 2 of message A1) B - (M -) A: half 1 of message B1 | hash (half 2 of message B1) A - (M -) B: half 2 of message A1 | hash (half 1 of message A1) B - (M -) A: half 2 of message B1 | hash (half 1 of message B1) ... and so on Nope, no good... M fakes the first message in both direction, and then he always has a good one, so he can compute the hashes. The only thing that might, as far as I can see, succeed (with a high probability) would be for everyone to hash the *next* half - meaning that, together with half 2 of message N, there will be the hash of half one of message N + 1. However, I don't see how this would be possible for an interactive communication... Thanks, Mark __ Do You Yahoo!? Yahoo! - Official partner of 2002 FIFA World Cup http://fifaworldcup.yahoo.com
Re: Diffie-Hellman and MITM
hi, If there is no previous shared secret,then ur communication on an insecure network is susecptable to the man in the middle attack. One solution suggested against the man in the middle attack is using the interlock protocol InterLock Protocol Is used to foil a man in the middle attack, 1:Alice sends Bob her public key 2:Bob sends Alice his public key 3:Alice encrypts her message with Bob's public key.She sends half of the encryped message to Bob. 4:Bob encrypts his message using Alice's public key.He sends half of the encrypted message to Alice. 5:Alice sends the other half of encrypted message to Bob. 6:Bob puts the 2 halves of Alice's message together decrypts it with his private key.Bob sends the other half of the message to Alice. 7:Alice puts the 2 halves of Bob's message together decrypt it with her private key. Here Mallory can still substitute his own public key for Alice Bob . Now when he interceprs half of Alice's message,he cannot decrypt it with his private key re-encrypt it with Bob's public key .He must invent a completely new message send half of it to Bob. When he intercepts half of Bob's message to Alice,he has the same problem. He cannot decrypt with his private key re encrypt with Alice's public key. By the time the second half of the message of Alice Bob arrive,its already too late to change the new message he invented. The conversation between Alice Bob need to be completely different. How ever if Mallory can mimic Alice Bob,they might not realise that they are being duped may get away with his scheme here is what i think It is not compulsary that all the blocks of messages must be invented by Mallory. he only need to make the first full message for alice and send it to bob vice versa. ok,eg: 1:alice send bob part of 1 st block 2:bob makes the 1 st half on his own and send to bob keeps alice's message 3:now bob sends his first half of message 4:mallory intercept it and make his own message and send it to alice 5:Again bob sends alice the other half of the msg which mallory intercepts substitue his own 2nd part of his block 6:the same happens when bob sends the second half of his message to alice,mallory intercepts it and sends his own 2 nd block to alice. since he has send one full block to each other has the full block of alice's and bob's true messages,mallory can now split it as half and complete the protocol ie, since the 1 st packet is fake,he has the true packets of alice bob can complete the protocol. All mallory would have to do is send the half of the (n th) packet when he receives the half of (n+1)th packet since the 1 st packet was faked by mallory. so i dont think the interlock protocol will work in this case. thats how i understand it. am i not rite? Regards Data. --- Mike Rosing [EMAIL PROTECTED] wrote: On Fri, 28 Jun 2002, Marcel Popescu wrote: Well... I assume an active MITM (like my ISP). He's able to intercept my public key request and change it. Plus, I now realize I should have put an even harder condition - no previously shared *information*, even if it's public. I need to know if two complete strangers can communicate securely over an insecure network, even if they communicate through an untrusted party. Wasn't there a protocol for two prisoners communicating through an untrusted guard? Can't be done. You must have multiple channels, and you need to hope that all of them can't be spoofed. A phone call, a newspaper ad, a bill board, a satallite link, any one of them might be spoofed. But to spoof *all* of them would be very hard. If you use some kind of security by obscurity method, you can do something once. but for general security, it's not possible to just go via the net without an out-of-band check. A public posting of the key id is a pretty safe way for a large company or organization. A .sig with your key id is another good way, it leaves traces all over the net for a long time. The point is that you have to leave some kind of trace that's checkable via an effective alternate channel. Otherwise, the MITM wins. Patience, persistence, truth, Dr. mike __ Do You Yahoo!? Yahoo! - Official partner of 2002 FIFA World Cup http://fifaworldcup.yahoo.com
lsfr with odd charecteristics
hi, Book says, a construction that involved computing LSFR's over a field of 'odd charecteristics' is insecure. Does that mean a register with odd number of bits is insecure which would mean a tap sequence which uses an odd degree polynomial is insecure? Regards Data. __ Do You Yahoo!? Yahoo! - Official partner of 2002 FIFA World Cup http://fifaworldcup.yahoo.com
Re: How can i check the authenticity of a private key
hi, I was helping a friend if mine with rsa key generation.if it helps u here it is. I am posting the mail which i sent to him. 1:Choose 2 large prime numbers p q 2:choose n=p*q z=(p-1)*(q-1) 3:choose a number relatively prime to z anc call it d. two numbers (a,b) are said to be relatively prime if gcd(a,b)=1 eg: (5,25) are not relatively prime coz 5 is gcd not 1 how ever (5,27) are relatively prime coz gcd is 1 In particualr a prime number is relatively prime to all the numbers except its multiples. 4:find e such that e*d=1 mod z here ' = ' means equalance or congrurnce not equal to. a ( congruent) b modulo c,if c/(a-b) or in other words if a/c gives remainder b 5:to encrypt plain text p,cipher text c is calculated as if ^ denote exponent c=p^e (mod n) 6:to decrypt, p=c^d(mod n) We take an example, It is just for the understanding of the reader uses very small numbers. choose p=3 q=11 hence n=3*11=33 z=(3-1)*(11-1)=20 we find e,such that 7*e(congruent)1 (mod 20),yeilds e=3 I will try explain with the same example. 7*e=1 (mod 20) means,find e such that 20/( (7*e)-1) For this we use the euclidean algorithm the euiler fermat theorom The eucledian algorithm simply find the gcd of 2 numbers. here our purpose of using it is to find gcd of 2 numbers see if they are relatively prime. Accoring to euiler-fermat theorom if gcd(a,m)=1, that is they are relatively prime then the solution (unique mod m) of the linear congruence ax (congruent) b (mod m) is given by x (congruent) b* ( a^(phi(m)-1)) (mod m) where phi(m) is the euiler totient function or the euiler phi function. if(a,m)=d,then it will have d solutions modulo m. how ever we are only interested in (a,m)=1,hence 1 solution mod m. well,Just a few defenitions Defenition of Euiler Totient If n=1 ,the euiler totient phi(n) is defined as the number of positive integers not exceeding n that are relatively prime to n. here are just a few examples if n=1 phi(1)=1 if n=2 phi(2)=1 (only 1 is relatively prime to 2) if n=3 phi(3)=2 (1 2 are relatively prime to 3) if n=4 phi(4)=3 (1,2,3 are ...) if n=5 phi(5)=4 (1,2,3,4 are...) if n=6 phi(6)=2 (1,5 are...) here is a usefull property 1 might need to apply some times phi(m*n)=phi(m)*phi(n) if gcd(m,n)=1 If a prime p does not divide a then a^(p-1) (congruent) 1 (mod p) now as in the example 7*e (congruent) 1 (mod 20) let us take e=x so, 7*x (congruent) 1 (mod 20) by eulier fermat theorom x(congruent) 1*(7^(phi(20)-1)) (mod 20) phi(20)=8.i.e there are 8 numbers less than 20 which are relatively prime to 20 This process of computing the euiler totoient is speeded up on a computer using the eucledian algorithm which finds gcd(a,b),for all a les than b count those a which are relatively prime to b whose sum gives the euiler totient. ok,so x (congruent) 1*(7^(8-1)) (mod 20) x (congruent) (7^7)mod 20 x (congruent) 823543(mod 20) 823543/20 gives remainder 3,that is 823543(mod 20)=3 therefore x=3 or e=3. this is how e is actually obtained in the above example. the rest of the encryption decryption are as mentioned above,i haven't continued the example with that part since i guess u only need to know how the key is generated. to encrypt we have 2 keys (e,n) to decrypt we have 2 keys (d,n) n=p*q is easy to calculate d is a number relatively prime to z choose a random d,test gcd(d,z) =1 using the euclidean algorithm,continue the process till u find one. the only othe key is e,which as above explained is found using the euiler-fermat theorom the euclidean algorithm. In this manner e,n,d can be found for large primes as well. Data. --- Mike Rosing [EMAIL PROTECTED] wrote: On Fri, 31 May 2002, surinder pal singh makkar wrote: I am a newbie in cryptography. What I have learnt till now is that in assymeric cryptography scenario we have a private key and we generate the public key corresponding to it and then we send it to the central agency. You don't have to send the public key to a repository, it's just convienient. Suppose after sometime I have a private key and the public key. Is there some software tool which can tell me whether the public key is the same corresponding to the private key I am having. Also is there some tool which can tell me whether the keys have been curropted or not With ECC you just recompute the public key from the private key and make sure it matches what's out in public. With RSA you just pick some random value (not zero or 1) and see if r^(e*d) = 1 mod N, or if you know p and q (where N = p*q) check that e*d = 1 mod (p-1)*(q-1). It's the same thing as encrypting/decrypting something to see if you get the same thing back. If not, something is wrong. I'm not sure how you can tell which key might be corrupted. For the public side, having the key reside in many places would do it - you
ANSI X9.17 STANDARDS
hi, I have an idea of what x9.17 standards says but no idea behind the mathametcial background of it. x9.17 standards is a standard but why is it so.mathametically what makes it a secure key generator? Could some 1 pls address the issue. Thank u very much. Data. __ Do You Yahoo!? Yahoo! - Official partner of 2002 FIFA World Cup http://fifaworldcup.yahoo.com
Mersenne Twister
hi, Does any 1 have a reference to the actual Mersenne Twister algorithm? Thank u. Regards Data. __ Do You Yahoo!? LAUNCH - Your Yahoo! Music Experience http://launch.yahoo.com
Regarding maximum period LSFR's
hi, Its regarding maximum period LSFR's (Linear feed back shift registers) used for generating pseudo random numbers. A tap sequence for an LFSR is the xor of certain bits in the register. For eg: I choose a primitive polynomail mod 2 x^32+x^7+x^5+x^3+x^2+x+1 is a primitive polynomial mod 2(chosen from a table) It says for an LSFR to be a maximum period LSFR, the polynomial from a tap sequence plus constant one must be a primitive polynomail mod 2 so polynomail from a top sequence+1= x^32+x^7+x^5+x^3+x^2+x+1 (as chosen earlier) How ever what is the polynomial formed the tap sequence how is it found,I dont understand. It further says the degree of the polynomail is the length of the shift register. Here 32 is the degree,hence is a 32 bit shift register. It says a primitive polynomial of degree n is irreducable polynomial that divides (x^2)^(n-1) +1 but not (x^d)+1 for any d that divides (2^n-1) Now what is the polynomial of degree n? I thought I already had one with degree 32. which is the primitive polynomial of degree n that divides (x^2)^(n-1) +1 but not (x^d)+1 for any d that divides (2^n-1) and where did it come from? Regards Data. __ Do You Yahoo!? LAUNCH - Your Yahoo! Music Experience http://launch.yahoo.com
Random number generator-Idea 1
hi, With reference to the following url http://www.ietf.org/rfc/rfc1750.txt As in idea 1 what about choosing 2 independent bit file streams. Then as in RFC 1750 6.1.1 A Trivial Mixing Function (page 14), make a 3rd bit file stream such that We xor For i=0 to n bit(i)file3=bit(i)file1 (xor) bit(i) file2 and follow idea 1? Is the problem solved and idea 1 worthy? Regards Data. __ Do You Yahoo!? Yahoo! Games - play chess, backgammon, pool and more http://games.yahoo.com/
Re:Two ideas for random number generators
hi, Using Transition Mappings to De-Skew Randomness Recommendations for Security RFC 1750 An extract from it. Another technique, originally due to von Neumann [VON NEUMANN], is to examine a bit stream as a sequence of non-overlapping pair | pair |probability | | 00 | (0.5 - e)^2 = 0.25 - e + e^2 | | 01 | (0.5 - e)*(0.5 + e) = 0.25 - e^2 | | 10 | (0.5 + e)*(0.5 - e) = 0.25 - e^2 | | 11 | (0.5 + e)^2 = 0.25 + e + e^2 | This technique will completely eliminate any bias but at the expense of taking an indeterminate number of input bits for any particular desired number of output bits. The probability of any particular pair being discarded is 0.5 + 2e^2 so the expected number of input bits to produce X output bits is X/(0.25 - e^2). Eastlake, Crocker Schiller [Page 12] RFC 1750Randomness Recommendations for SecurityDecember 1994 This technique assumes that the bits are from a stream where each bit has the same probability of being a 0 or 1 as any other bit in the stream and that bits are not correlated, i.e., that the bits are identical independent distributions. If alternate bits were from two correlated sources, for example, the above analysis breaks down. The above technique also provides another illustration of how a simple statistical analysis can mislead if one is not always on the lookout for patterns that could be exploited by an adversary. If the algorithm were mis-read slightly so that overlapping successive bits pairs were used instead of non-overlapping pairs, the statistical analysis given is the same; however, instead of provided an unbiased uncorrelated series of random 1's and 0's, it instead produces a totally predictable sequence of exactly alternating 1's and 0's. A few doubts regarding the above. Another technique, originally due to von Neumann [VON NEUMANN], is to examine a bit stream as a sequence of non-overlapping pairs What do they mean by bit stream as a sequence of non-over lapping pairs? Also isn't idea-1 of my earlier post Two idea's for random number generators very similar to this? www.neo.ircsuper.net Wouldn't the problem in idea 1 be solved if I choose a bit stream as a sequence of non-over lapping pairs? If we choose bits that are from a stream where each bit has the same probability of being a 0 or 1 as any other bit in the stream and that bits are not correlated, i.e., that the bits are identical independent distributions. Would n't idea 1 work? Regards Data. __ Do You Yahoo!? Yahoo! Games - play chess, backgammon, pool and more http://games.yahoo.com/
Need help on x mod m
hi, Here is a query frm my friend- I wondered if anyone knows a solution for my problem... x mod m = a x mod n = b Let's say i choose small number... m=5 n=3 a=3 b=1 then it's x mod 5 = 3 x mod 3 = 1 after trying a but you will now that x=13 but how can i solve it easier than trying all kinds of number. I mean a non-trivial solution. I think the effort gets too huge for larger numbers like: x mod 739631974298624487 = 403861151213590046; x mod 898793745643687546 = 206683840814855797; x=37658765832565679345651 And I want to use it at least with 128bit numbers. what would be a non-trivial method of solving x in the above example. Thank u Regards Data _ __ Do You Yahoo!? Yahoo! Games - play chess, backgammon, pool and more http://games.yahoo.com/
Two ideas for random number generation
hi, Here are two ideas which came up in my mind. Since I have done a few diagrams for illustration and thought that it will not be a good idea as attachment,I have put the ideas at the following url http://www.ircsuper.net/~neo/ I sincerely appreciate ur comments.Thank u for ur time. Regards Data. __ Do You Yahoo!? Yahoo! Games - play chess, backgammon, pool and more http://games.yahoo.com/
