In complement to Kosmonaut's answer, I'd like to add a few pieces to the jigsaw puzzle.
The undisputed etymology of the English noun screw is from Middle French "escroe" (pronounced "escrow") which evolved into present-day French "écrou" (pronounced a-crew) and designates the nut (of a bolt). Its use in English is recorded as early as ca 1400.
Interestingly enough there are in present-day French a number of expressions related to the jail system bearing the word "écrou".
- écrouer: to imprison.
- registre d'écrou: the register log where new incarcerations and releases are recorded along with the cause of imprisonment.
- numéro d'écrou: the unique id for a prisoner in a given jail.
- levée d'écrou: the release of a prisoner (literally raising the screw).
From there one is faced with two different and possibly complementary explanations because the Old French word escroe has two different meanings, each with its own etymology.
The first (ca 1160) meaning of the Old French word escroe is that of a scroll to which new strips (called escroeles) of parchment where appended when more room was needed. From this meaning comes the posterior English words scroll and escrow. This meaning in turn evolved to also designate various royal administration registers (for instance "écroues des dépenses du Roy"). Another of these registers was used to keep track of the imprisonments and releases of prisoners. Hence the "registre d'écrou" and the word "écrouer".
Oddly enough the second meaning (16th century) of the Old French word escroe is that of the common screw. Although the etymology is still disputed, the most convincing theory is that of an analogy with the genitals of the swine and the boar (the penis of a boar is shaped like a cork-screw and the swine cervix matches that shape). The Latin word for a breeding swine is scrofa 1, 2.
So how does the screw relate to a key?
First one has to take into account the fact that many prisoners were not only locked in cells (either individual or collective) but also shackled and chained to the wall (in older times when locks were expensive to produce, they were just chained) and that involved shackle riveting and later screwing (for screw pin shackles). There are a number of collectors shackles that can illustrate this "technology" - here is a randomly selected sample (of which I include the pictures below in case it goes away). One can guess how it works: the screw must first be removed so that the key can open the shackles.

Note 1:
In Icelandic the word for screw is
skrúfa (very close to the Latin
scrofa) and incidentally also means "to mount a female". In Spanish, the screw nut is
tuerca whilst the swine is
puerca.
Note 2:
See also the etymology of
porcelain for another word involving the swine genitals.