None of this basic stuff has been classified since 1945.
The basic idea driving the atomic bomb is not E=mc^2 — that just explains where the energy _ultimately_ comes from, it does not tell you how to make an atomic bomb or whether one is at all possible (any more than F=ma tells you that it is possible to go to Mars).
In late 1938 it was discovered through scientific research that was in no way trying to produce anything "practical" that uranium atoms could be split by neutrons (Hahn and Meitner et al.). This came as a considerable surprise to the people who discovered it and everyone else working on similar work with neutrons — it was just not assumed that something as small as a neutron could split something as large as uranium. (As is often the case in the history of science, while the discovery itself was a surprise, the body of work it fit into was well-established — namely, scientists taking a newly discovered particle, the neutron, and shooting it at stuff to see what happened. The particular Hahn/Meitner/etc. work was meant to help clarify some results from a few years earlier by Fermi, and ended up, to everyone's surprise, totally contradicting them.)
Other scientists (e.g. Bohr and Wheeler) quickly realized that what was happening was that the uranium-235 isotope in particular had just the right mixture of protons and neutrons in its nucleus, and so just a little jostling from a neutron was likely to split it apart. That mixture of protons and neutrons determines everything: a uranium-238 isotope, for example, tends _not_ to split when it absorbs a neutron, it instead just becomes uranium-239. (The scientists didn't choose the isotope — they _identified_ that it was only the uranium-235 isotope that was splitting in their samples.)
Once they understood how the splitting worked, it became possible to predict which isotopes would also split. For example, having an odd atomic number helps a lot (235 not 238). That limits the possible elements by a lot. For the purpose of making a bomb, you have to know which isotopes you can actually refine or produce. Uranium-235 is found in nature, but takes considerable effort to separate from uranium-238. Radiochemists realized that if you shot neutrons at uranium-238, though, it would turn into uranium-239, which would itself undergo radioactive decay a few times and become plutonium-239. The latter was also predicted to be fissionable (and it was). So if you had a large source of neutrons, you could turn lots of uranium-238 into uranium-239. The development of the nuclear reactor provided that source of neutrons.
As for how they decided to make the bomb — it's a long story with a big history to it! Try picking up a copy of Rhodes' _The Making of the Atomic Bomb_ if you want a nice popular version of it. The short answer is that it did not take long for scientists worldwide to realize that if you can split an atom with neutrons, and it releases _more_ neutrons in the process, then you can set up a chain reaction that will release _a lot_ of energy. This can be used either in a reactor (a controlled chain reaction) or in a bomb (an uncontrolled one). Both of these prospects interested scientists globally. It seemed plausible to all that you could, in a short amount of time, develop a prototype nuclear reactor. Could you really make a bomb out of it? That was hard to know, and in fact only one nation, the United States, committed to actually doing so during the war.
Why'd they commit to do this? Because scientists worried that their enemies (the Germans) were doing the same thing, and convinced government officials that it was worth spending a lot of money and time and labor on developing this weapon. They also (somewhat amusingly in retrospect) thought it would be a lot easier than it was (the Germans, funnily enough, were a bit more on the mark about the difficulty of the job, and didn't think it was worth committing to during wartime). The context of this scientific work was not done in a vacuum: it was being done during the bloodiest conflict of the 20th century, and that motivated a _huge_ amount of scientific research and industrial development around this new discovery.
None of this was "random" (though sometimes there are, historically, coincidences). It only appears random because you haven't read much on it. There are _many_ works out there that describe the development of this science and the subsequent technological developments that came from it. It was not at all a few random guesses — it was the creation of an entirely new industry from scratch, with the labor of many thousands of scientists working together, and the labor of many _hundreds of thousands_ of everyday people constructing and operating the plants necessary. Rhodes' book is a great starting point — check it out!