Notices
Results 1 to 27 of 27

Thread: Codes and ciphers

  1. #1 Codes and ciphers 
    Guest
    Any interest in this forum for codes and ciphers?


    Reply With Quote  
     

  2.  
     

  3. #2  
    Universal Mind John Galt's Avatar
    Join Date
    Jul 2005
    Posts
    14,169
    30 27 8A 14 56 91


    Reply With Quote  
     

  4. #3  
    Forum Senior
    Join Date
    Mar 2006
    Posts
    309
    obviously X=81094
    I don't suffer from insanity, i enjoy every minute of it

    the road to succes is never paved or clearly marked
    Reply With Quote  
     

  5. #4  
    Forum Freshman lince!'s Avatar
    Join Date
    Sep 2006
    Posts
    28
    yup, and RSA as well
    is there any thread on this topic before?
    Reply With Quote  
     

  6. #5  
    Forum Professor river_rat's Avatar
    Join Date
    Jun 2006
    Location
    South Africa
    Posts
    1,497
    Lol - i have a one million dollar prize for anyone interested in RSA
    As is often the case with technical subjects we are presented with an unfortunate choice: an explanation that is accurate but incomprehensible, or comprehensible but wrong.
    Reply With Quote  
     

  7. #6  
    Forum Bachelors Degree The P-manator's Avatar
    Join Date
    Nov 2005
    Location
    Toronto
    Posts
    474
    I love cryptography.
    Pierre

    Fight for our environment and our habitat at www.wearesmartpeople.com.
    Reply With Quote  
     

  8. #7  
    Forum Freshman lince!'s Avatar
    Join Date
    Sep 2006
    Posts
    28
    Quote Originally Posted by river_rat
    Lol - i have a one million dollar prize for anyone interested in RSA
    that is cool,man.
    is it the one which asks for factorizing a thousand digit number?
    Reply With Quote  
     

  9. #8  
    Forum Bachelors Degree The P-manator's Avatar
    Join Date
    Nov 2005
    Location
    Toronto
    Posts
    474
    How is that possible?
    Pierre

    Fight for our environment and our habitat at www.wearesmartpeople.com.
    Reply With Quote  
     

  10. #9  
    Forum Professor river_rat's Avatar
    Join Date
    Jun 2006
    Location
    South Africa
    Posts
    1,497
    Quote Originally Posted by lince!
    is it the one which asks for factorizing a thousand digit number?
    No, it is proving that RSA is secure - otherwise known as the P=NP problem.
    As is often the case with technical subjects we are presented with an unfortunate choice: an explanation that is accurate but incomprehensible, or comprehensible but wrong.
    Reply With Quote  
     

  11. #10  
    Forum Radioactive Isotope MagiMaster's Avatar
    Join Date
    Jul 2006
    Posts
    3,440
    Aka, proving the existence of one-way functions, right? BTW, why can't PSPACE-complete problems be used to generate one way functions (by constructing an instance with the desired answer)? Obviously NP-complete problems would only work if P!=NP, but is there something else against using PSPACE or EXPTIME-complete problems?
    Reply With Quote  
     

  12. #11  
    Forum Professor river_rat's Avatar
    Join Date
    Jun 2006
    Location
    South Africa
    Posts
    1,497
    Its rather to prove that the multiplying two large primes together gives you a one-way function (i.e. factorising is hard!).

    How would you encrypt data quickly with a PSpace-complete problem? RSA works because the mod arithmatic is quick.
    As is often the case with technical subjects we are presented with an unfortunate choice: an explanation that is accurate but incomprehensible, or comprehensible but wrong.
    Reply With Quote  
     

  13. #12  
    Forum Freshman lince!'s Avatar
    Join Date
    Sep 2006
    Posts
    28
    hey, I am interested in the number theory applied in cryptography but i don't know much.
    is that 'mod arithmetics' you are referring to 'euclidean algorithm?
    Reply With Quote  
     

  14. #13  
    Forum Radioactive Isotope MagiMaster's Avatar
    Join Date
    Jul 2006
    Posts
    3,440
    Well, I was thinking something along the lines of generating an instance of a very hard problem (NP-complete or PSPACE-complete or something) such that it provable has only one solution (which would be your private key). Then that problem instance would be your public key. I don't know exactly how you'd go about applying the two though. Also, I don't know if generating such an instance would compromise its hardness....
    Reply With Quote  
     

  15. #14  
    Forum Professor river_rat's Avatar
    Join Date
    Jun 2006
    Location
    South Africa
    Posts
    1,497
    The NP idea is exactly what RSA does (EDIT: finding a prime factor is a np problem). But if NP = P then RSA is not secure as you could rapidly break the encryption.

    The problem with PSpace problems (or anything higher then NP) is that i dont think that you can check solutions on polynomial time - the fact that these problems are non-deterministic polynomial time complex is important.
    As is often the case with technical subjects we are presented with an unfortunate choice: an explanation that is accurate but incomprehensible, or comprehensible but wrong.
    Reply With Quote  
     

  16. #15  
    Forum Sophomore
    Join Date
    Jul 2005
    Posts
    121
    Quote Originally Posted by river_rat
    ... (finding a prime factor is a np-complete problem).....
    Since when? Factoring is obviously NP, but I've always thought it wasn't known to be NP-complete (or in P of course).

    factoring being in P wouldn't mean RSA is sunk either. It's just a statement about asymptotic bounds for the run-time of the algorithm, what happens in the range of the inputs used in practice is what's more important. If you had a factoring algorithm that takes 10^100*n^10000 steps, n the number of digits, this is going to be worse than whatever non-polynomial time algorithm we currently have if you were trying to attack the rsa challenge numbers for example. For 'large enough' inputs the polynomial time algorithm will win, but 'large enough' may be a long way off.

    from the other direction, if you could show factoring is not in P it wouldn't necessarily mean rsa is secure.
    Reply With Quote  
     

  17. #16  
    Forum Professor river_rat's Avatar
    Join Date
    Jun 2006
    Location
    South Africa
    Posts
    1,497
    oops you're right - call it a brain fart. What i meant was proving NP=P would prove factoring is P.

    parallel processing is important for the discussion though - given a P algorithm and a large server farm you could still handle the large multiplying factors. Well at least within reason.
    As is often the case with technical subjects we are presented with an unfortunate choice: an explanation that is accurate but incomprehensible, or comprehensible but wrong.
    Reply With Quote  
     

  18. #17  
    Forum Sophomore
    Join Date
    Jul 2005
    Posts
    121
    That's true even without a polynomial time factoring algorithm. The various sieve algorithms scale very well with parallel processing, so given enough hardware your can factor a given number in as short a time as you like (some restrictions on communication between computers and organizing the whole thing of course).

    The resources of your attackers are always under consideration when worrying about security.
    Reply With Quote  
     

  19. #18  
    Forum Professor river_rat's Avatar
    Join Date
    Jun 2006
    Location
    South Africa
    Posts
    1,497
    Your benifit when using parallel processing with a polynomial time algorithm is quite a lot better (in general) then with an exponential time algorithm - given as much computer power as we have at the moment, factorising RSA 2048 would still take a while (even with a general number field sieve the number of calculations is of the order 10^14)
    As is often the case with technical subjects we are presented with an unfortunate choice: an explanation that is accurate but incomprehensible, or comprehensible but wrong.
    Reply With Quote  
     

  20. #19  
    Forum Sophomore
    Join Date
    Jul 2005
    Posts
    121
    Quote Originally Posted by river_rat
    Your benifit when using parallel processing with a polynomial time algorithm is quite a lot better (in general) then with an exponential time algorithm
    Why? Does doubling the number of processors do better than halve the time needed for a polynomial time algorithm?
    Reply With Quote  
     

  21. #20  
    Forum Professor river_rat's Avatar
    Join Date
    Jun 2006
    Location
    South Africa
    Posts
    1,497
    Im comparing the growth of p(n)/n (p(n) a polynomial) to e^p(n)/n - hence the general comment.
    As is often the case with technical subjects we are presented with an unfortunate choice: an explanation that is accurate but incomprehensible, or comprehensible but wrong.
    Reply With Quote  
     

  22. #21  
    Forum Sophomore
    Join Date
    Jul 2005
    Posts
    121
    Quote Originally Posted by river_rat
    Im comparing the growth of p(n)/n (p(n) a polynomial) to e^p(n)/n - hence the general comment.
    I don't follow you. How is this comparing multiple processors for a polynomial time algorithm vs. an exponential time algorithm (or other)? Are you suggesting the number of processors available is related to the input size??
    Reply With Quote  
     

  23. #22  
    Forum Professor river_rat's Avatar
    Join Date
    Jun 2006
    Location
    South Africa
    Posts
    1,497
    No - its just so that i am comparing the same processor growth rates in both cases. Feel free to substitute your own growth function, it was just the simpliest one i could think of.
    As is often the case with technical subjects we are presented with an unfortunate choice: an explanation that is accurate but incomprehensible, or comprehensible but wrong.
    Reply With Quote  
     

  24. #23  
    Forum Sophomore
    Join Date
    Jul 2005
    Posts
    121
    Okie- doubling the number of processors will halve the time it takes to run a quadratic sieve (for example). the run time of this algorithm is totally irrelevant to how adding more processors affects the total time, double processors=>halves time (not quite, but close enough).

    This is why I'm confused that you would say a polynomial time algorithm would benefit more from parallel processing. I don't see why you would link the input size and the number of processors and say this is still a comparison between how multiple processors affect the time when the input sizes are changing along with the number of processors. You're essentially saying "given access to the same hardware, the poly. algo. is better than the exp. algorithm as the input size grows." This is of course true and has nothing to do with parallel processing.

    Of course there's also no guarantee a poly. time algorithm would benefit at all from parallel processing.
    Reply With Quote  
     

  25. #24  
    Forum Professor river_rat's Avatar
    Join Date
    Jun 2006
    Location
    South Africa
    Posts
    1,497
    I thought we were comparing best hardware examples for an attacker?

    A polynomial algorithm does not benifit more or less or in any general way (as that depends on the algorithm), what i am saying is that you can in general get a polynomial time algorithm to give you results within reasonable time using parallel processing as compared to an exponential time ones given the same hardware for both.
    As is often the case with technical subjects we are presented with an unfortunate choice: an explanation that is accurate but incomprehensible, or comprehensible but wrong.
    Reply With Quote  
     

  26. #25  
    Forum Sophomore
    Join Date
    Jul 2005
    Posts
    121
    Quote Originally Posted by river_rat
    I thought we were comparing best hardware examples for an attacker?
    err, sure.

    You started comparing how parallel processing affects a poly. vs. exp. algorithm with:

    Quote Originally Posted by river_rat
    Your benifit when using parallel processing with a polynomial time algorithm is quite a lot better (in general) then with an exponential time algorithm...
    but now you say:

    Quote Originally Posted by river_rat
    A polynomial algorithm does not benifit more or less or in any general way (as that depends on the algorithm), ...
    These are saying completely different things to me. the second I agree with, not the first.

    Quote Originally Posted by river_rat
    ...what i am saying is that you can in general get a polynomial time algorithm to give you results within reasonable time using parallel processing as compared to an exponential time ones given the same hardware for both.
    This only depends on how long it takes to get the result for the given input on 1 cpu and not at all on whether it was a polynomial time or an exponential time algorithm (this is assuming both scale with more processors).
    Reply With Quote  
     

  27. #26  
    Forum Professor river_rat's Avatar
    Join Date
    Jun 2006
    Location
    South Africa
    Posts
    1,497
    They say different things because they mean different things - perhaps im not being very clear here - its late my side of the world.

    First quote - benefit in relation to the poor guy waiting for the response given the best server farm he can afford.

    Second quote - benefit wrt to actual processing of the algorithm, some algorithms parallelise well and others dont.

    My point is that in general p(n) < e^q(n) for a random p and q and thus your "wait time" is less for P programs then for Exptime ones.
    As is often the case with technical subjects we are presented with an unfortunate choice: an explanation that is accurate but incomprehensible, or comprehensible but wrong.
    Reply With Quote  
     

  28. #27  
    Forum Radioactive Isotope MagiMaster's Avatar
    Join Date
    Jul 2006
    Posts
    3,440
    Well, the thing is there is a tendency for polynomial algorithms to improve over time.

    Anyway, my idea with the PSPACE-complete problem is that would certainly take exponential time to work out a solution. Would it actually be a problem that it would take a long time to work out if a given solution works or not? Assuming you built the instance in such a way that you know what the solution is, couldn't you use that as a key?

    I suppose an NP-complete problem would be good in that a given solution could be checked quickly, but it would still be hard to find a solution. (Again assuming P != NP.) In either case, how would you go about building a public key system with it though?
    Reply With Quote  
     

Bookmarks
Bookmarks
Posting Permissions
  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •