Jump to content

  • Log In with Google      Sign In   
  • Create Account


Member Since 28 Feb 2011
Online Last Active Today, 05:05 AM

#5291252 Getting objects within a range (In order, fast)

Posted by Bacterius on 12 May 2016 - 12:04 AM

What you want is called a range search, and there are efficient data structures for it. A good one is the kd-tree, which has an efficient range search algorithm associated with it, so take a look at that if you have the time.

#5289935 Time - the most important factor.

Posted by Bacterius on 03 May 2016 - 01:53 PM

Take a look at your computer's mouse. It has a few base mechanics: you move the mouse and that moves the cursor on your screen, you can click, sometimes they have a scroll wheel, but overall seem to do pretty basic things. And they've been around for a while now. What could be simpler? What if I told you this simple-looking item actually took months of work to research, develop, prototype and manufacture, to design both the hardware inside it that you don't see, and also the external interface, for ergonomy and so on, as well as all the branding and marketing which allowed you actually find and buy it? It probably took years worth of man-hours to bring this simple little item to your desk.


What this analogy is meant to illustrate is that just because something is simple to use, doesn't mean it was simple to make.

#5289605 router programming

Posted by Bacterius on 01 May 2016 - 01:35 PM

Another less intrusive option is to use the Linux TUN/TAP module to create a virtual ethernet network interface in which you receive raw ethernet packets and have to parse them, read their MAC addresses and route them, do ARP and all that. Then you just set up a bridge (or something) between your public-facing interface and that virtual interface and you can implement whatever logic you want. This is considerably harder than just making a virtual IP interface where you receive IP packets though.

#5289052 Detect if someone is live-streaming the game

Posted by Bacterius on 28 April 2016 - 01:11 AM

If so then don't bother detecting it; just provide a known shortcut that live-streamers can toggle to enable livestream features. Less hassle, more predictable :)

#5285909 RSA message limitation (with C++ source code)

Posted by Bacterius on 08 April 2016 - 03:20 PM

Is it more secure to encrypt multiple times... like triple DES, but using RSA?


If you need multiple layers of encryption to make an algorithm secure, it's probably not worth using. So, no. BTW, you very rarely encrypt actual messages with RSA, usually you encrypt a random key that is used to encrypt the bulk of the data with a faster symmetric algorithm like AES.

#5284799 RSA message limitation (with C++ source code)

Posted by Bacterius on 02 April 2016 - 04:39 PM

So, it's periodic like a sine wave?


It's periodic in the same way that the sequence of integers modulo 3 looks like 0 1 2 0 1 2 0 1 2 0 1 2 ... if you take any integer and add 3, the result modulo 3 won't change :)


Technically the exponent is periodic modulo lcm(p - 1, q - 1) which is smaller than (p - 1)(q - 1) but there is not much difference, the lcm is usually within a small factor of the product depending on how many factors p - 1 and q - 1 share.

#5284721 Wotsit.org

Posted by Bacterius on 02 April 2016 - 01:55 AM

Yeah, looks like it died in early august 2015 according to the Internet Archive. Regrettably web archivers were forbidden to crawl and index the downloads on the site because of this explanation on the Wotsit site (emphasis mine):

The download blocker will prevent any access to files on this site unless they present a valid HTTP_REFERRER tag - certain downloaders, poorly set up proxy servers and also selecting 'Save Target As' in MS Internet Explorer fail to give this information and so are blocked.

Please disable downloaders and open the links as normal.


The action of installing the download blocker was in response to several other file formats sites linking directly to files at wotsit.org and so "stealing" the bandwidth that Wotsit's Format has to pay for.

The volume of traffic through Wotsit's Format means that it has to be hosted on a commercial server which is paid for by the advertising banner revenues. The site has been making a loss since moving to the .ORG domain. People linking directly to files on the site bypass the pages with the banners on and do not contribute to the funding of the site.

I know the download protection causes problems for several users of the site but it is necessary in order to ensure the site continues to be funded... and so continues to exist.



This script was introduced in the late 90's, and is somewhat ironic in that the same web archivers which were denied access to the site's resources because they were considered to be hurting the site's growth, would have been able to preserve the site's content after it went down. It might be worth trying to contact the author (Paul Oliver, I believe) to ask if he has any backups he is willing to share, should you care enough.


Anyway, you might find some other useful resources here: http://justsolve.archiveteam.org/wiki/Sources

#5284324 RSA message limitation (with C++ source code)

Posted by Bacterius on 30 March 2016 - 02:06 PM

The two books I have "Applied Cryptography" by Bruce Schneier and "Mastering Algorithms with C" by Kyle Loudon both say that e must be coprime with (p - 1)(q - 1), not (p - 1) and (q - 1).


They are equivalent. e is coprime to (p - 1)(q - 1) if and only if it is coprime to both (p - 1) and (q - 1). :)

#5284321 RSA message limitation (with C++ source code)

Posted by Bacterius on 30 March 2016 - 01:46 PM

I am not aware of an attack that could exploit e being a small number. But what's wrong with making e be a random number between 0 and p*q? Technically you would have to verify that you didn't pick a multiple of p or q, but let's not worry about things that will not happen. :)


It has to be coprime to both p - 1 and q - 1, otherwise the security is considerably weakened and/or the encryption is not reversible. Practically speaking the reason we use 3, 17 or 65537 for e is because they have a low Hamming weight (due to being of the form 2^N + 1) which means that exponentiation by such e can be made very efficient (log2(e) exponentiations and 1 multiplication, which is optimal). This is virtually the only technical redeeming quality of RSA in the era of elliptic curve cryptography because properly-optimized RSA encryption with public exponent 3 is actually faster than ECC. Really, the only public exponent you should be using is 3, anything else comes from the misguided idea that small e are weak; they are not with proper padding, to the best of our knowledge, and to be honest, if there is a vulnerability with e = 3, there is probably also a vulnerability with any small e.


Also keep in mind that many RSA implementations will not necessarily function with arbitrary e; they may be configured to operate with only a restricted set of small standard exponents. Furthermore using a random e opens you up to a bunch of new attack vectors, in particular side channel attacks: you need to generate your e from something, probably the same source you generated your p and q from, so that gives you one more thing to screw up that an adversary can exploit. I would strongly discourage the use of a random e unless you like your encryption being unnecessarily slow and/or broken.


I think one of the main reasons people got the idea that using a small public exponent was a bad idea was the related-message attack that was popular a while back. Basically if you use plain RSA to send the same message to "e" different people with the same public exponent "e", then the message can be recovered by using each recipient's public key through a nice number-theoretic algorithm. But, of course, this only works because no padding scheme was used, and without secure padding there are far worse attacks that await you anyway.

#5283969 Joining data to bigger UDP packets?

Posted by Bacterius on 28 March 2016 - 07:30 PM


Generally large UDP packets (say larger than 1400 bytes or so, possibly less) will not survive a trip over the public internet

This is not generally true.

IPv4 will fragment and reassemble the packet if it's bigger than MTU, which will generally work fine (it may increase packet loss a small bit.)
(This is, unless you manually set the "don't fragment" bit on the packet.)

IPv6 does not have routers perform IP fragmentation, but instead lets each sending end create the fragments. Well-behaved IPv6 stacks will implement MTU discovery and do the fragmentation for you.

You should be confident that, unless you're using a really crappy network implementation, a UDP packet of any size (up to the limit of 65536 bytes) will be delivered to the other end, with a slight increase in packet loss as sizes go up.

If you run on a really crappy network implementation, IP datagrams of up to 1280 bytes will always be forwardable, which leaves 1272 bytes for your UDP payload before fragmentation is even an issue.

(Back in the days, dial-up modems had a smaller MTU of typically 576 bytes; it was recommended to keep packets below that, but larger packets still worked.)



We tried sending large UDP datagrams over ipv4 between Europe and NZ over the course of a week or so a few months ago and the packets were consistently lost (100% packet loss) when they exceeded a certain size and went through fine below that size. No special configuration was done on the network stacks. I don't exactly remember the threshold but it was around 1300-1400 bytes. Now it could have just been malfunctioning equipment (I will try and replicate it tonight to see if it's still happening) but in my experience large packets, let alone 65536-byte packets, are unreliable at best over long distances. Over short distances though I assume anything should work given a decent network infrastructure.

#5283943 Joining data to bigger UDP packets?

Posted by Bacterius on 28 March 2016 - 04:33 PM

Generally large UDP packets (say larger than 1400 bytes or so, possibly less) will not survive a trip over the public internet and will end their journey when they encounter a router that refuses to fragment them. If they do get through, they have a larger chance of being lost as any fragment being lost means the entire packet is lost.


It is best to send reasonable-sized UDP packets if you don't control the network path on which the datagrams will transit over: as big as possible (to limit IP/UDP overhead) but not too big that they will get fragmented or dropped. This is why you should try and remove as many redundancies as possible from your packets and limit any protocol overhead from your serialization method.

#5283480 RSA message limitation (with C++ source code)

Posted by Bacterius on 25 March 2016 - 05:15 PM

I read somewhere that if used incorrectly, RSA has the security of the lowly Caesar cipher. To get around this, one is supposed to add a pad of (pseudo-)random numbers to the message. Do you put the pad at the beginning of the message, or at the end? Or both?



#5282279 How to abort a file transfer immediately?

Posted by Bacterius on 20 March 2016 - 11:51 PM

Let's say I did that, now I am sending a file through the first socket, and after a while I decided to abort the file transfer, so I send the string "file transfer aborted" through the second socket and then this string is received by the other end, what should the other end do now?


The second end can then "gracefully" close his socket and let the OS clean up in the background while it moves on to other stuff since it now knows the transfer is aborted. That's if you really want to close it gracefully; like I said, if you need to tear down a connection NOW and don't care what happens to the data already committed to the TCP stream, then a hard shutdown is acceptable (to be fair, such situations are rare; when transferring large files it is common to transfer them block by block with, depending on your requirements, periodic status and integrity checking, which allows you to send control information over the same socket with minimal latency).

#5282273 How to abort a file transfer immediately?

Posted by Bacterius on 20 March 2016 - 11:14 PM

Yes, that is what "gracefully" means. Another way could be to keep a separate connection with another socket over which you send control information ("file transfer started", "file transfer complete", "file transfer aborted" and so on).


Also, ungracefully closing a TCP connection is not inherently bad, it's only bad in that you may lose buffered data or data in transit that, from the application's perspective, has already been sent (unless the application implements its own acknowledgment protocol on top of TCP). If you're aborting a transfer, you presumably no longer care if the file arrives intact, so it's okay. Just make sure the remote can distinguish between a completed transfer and a prematurely aborted transfer, and make sure the socket is not used for anything else.

#5280659 A ray with an ending position?

Posted by Bacterius on 11 March 2016 - 02:55 AM

A ray with an ending position is called a segment.