/u/schuylertowne has a relevant comment from a past thread

For the past 200-ish years it has been generally believed that the first key-based locks originated in Egypt ~2000BCE. However, recently there has been strong evidence emerging to place its invention in Mesopotamia, though the timeline is roughly the same.

There were a couple big pieces of evidence to point to Egypt, but what specifically led to the re-introduction of the pin-lock to modern, European society were the journals of Vivant Denon, an archeologist, artist and historian who traveled with Napoleon's "corps des savants" a collection of 151 scholars from a wide range of disciplines who toured Egypt when Napoleon invaded. Vivant was fairly adventurous and fascinated by Egypt, so, when a small contingent of soldiers were tasked with chasing after Murad Bey, a guerrilla fighter, he requested permission to separate from the rest of the corps to travel with them into upper Egypt.

He kept well detailed, and usually well illustrated, journals throughout his time in Egypt, but unfortunately when he arrived at the Temple in Karnak the heat was too oppressive to stay in the open long enough to sketch, but he did offer this description:

"Among the new discoveries which I made while traversing the ruins of the temple, may be mentioned a figure that I perceived on the outer walls of the small buildings by the side of the sanctuary; the figure represents a person making an offering of two obelisks. I saw also delineated the gate of a temple, with two folding doors, shut by exactly the same kind of wooden locks that are at present made use of." --Travels in Upper and Lower Egypt by Vivant Denon, translated by Arthur Aikin

Later on in his journals he waxes a bit poetic, talking about how incredible it is that this lock retained its exact form for thousands of years and was still in use by the locals. When his journals were translated and published in England they ignited a huge interest in the pin-lock which, though still in use in parts of the world in very primitive forms, had been generally forgotten or ignored in any industrial societies. The lock Denon saw carved on that wall bears an incredible resemblance to the lock that is very likely on your door (though it is quite different than the one in your car).

While Denon mentions in his journal that the oppressive heat on the day they arrived in Karnak was such that he could not stop to make an illustration of the relief, he does give us enough clues to guess that he was surveying the Palace of Ma'at, where there is a well preserved relief of Thutmose III making an offering of two large obelisks. (Thanks to Elaine Sullivan at the Digital Karnak project for pointing this out) The Palace of Ma'at was built by Hatshepsut who reigned for more than 20 years in the middle of the 15th century BCE. Even if the relief did depict a pin lock, at the time of Denon's discovery it would have only suggested an age of 3200 years, not the 4000 oft-repeated by lock historians.

What is puzzling, though, is that there is very limited information on how the pin lock actually came into existence, what it evolved from, or how it was first imagined. However, in the last 25 years there has been a small pocket of scholarship investigating the puzzle of the origin of the lock from a linguistic perspective. Prior to 1990 the general opinion was that the ancient Mesopotamians did not have sophisticated mechanical locks, but instead only bolts, doors, latches, etc. There hadn't been any artifacts to support the idea of the existence of a key-based lock.

However, in 1990, Dr. Daniel Potts published a brief paper in the Italian journal "Mesopotamia" in which he suggested the existence of "The Egyptian Lock" in Mesopotamia by laying out new definitions for a few cuneiform words. There was a "constellation of terms" that had proved difficult to nail down. When applied to bolts or door seals there were some odd redundancies. Dr. Potts:

"The difficulty of identifying these parts correctly lies, to begin with, in the choice of the correct lock system as a model, and thereafter in finding identifications which, in association with all of the other relevant terms, make mechanical sense. In contrast to Leichty and Scurlock, I propose to use the Egyptian lock as a model for the identification of the most important terms." --Daniel Potts, Lock and Key in Ancient Mesopotamia

By “Egyptian lock” he was, of course, referring to the early pin lock. Using the pin lock as a model he was able to create coherent translations of several specific cuneiform passages. Of particular note was an ancient complaint found in a passage labeled “CT 40 12:7-15.” Using the pin lock for context, we can see that the complaint charges that the pins (or sikkatu) in the lock (namzaqu) of the Istar temple weren’t properly aligned with the pin chambers (uppu) in the bolt (aškuttu). This, as any modern locksmith would know, prevented the proper operation of the lock.

Sikkatu, here, is particularly exciting, because that word had been used by the Mesopotamians even earlier, to mean something slightly different. Before the Egyptian Lock there were Door Seals. These were just a wooden peg, shoved through a door and secured with a clay seal. You could easily open the door by destroying the seal, but at least then the owner would have known it was broken into. The word for the peg in the door seal was also "Sikkatu" so, now we have a clear linguistic evolution from one concept to the next, which implies a mechanical evolution. But, when did that occur?

To answer that I got in touch with Dr. Karen Radner at the University College in London, she had this to say:

"The title rab sikkāte is attested already in the Old Babylonian period which would seem to indicate that the lock with bolt-pins was in use at the time (c. 18th century BC). But for lack of earlier sources, both textual and archeological, it is difficult to say whether this type of lock was an innovation of that time or whether it had been introduced before that. In the mid-third millennium, however, architectural remains (of temples) indicate that the older lock type was used. So the "modern" locks must have been introduced sometimes after that and before 1800 BC."

So, the transition from door seals to key-based pin locks happened in Mesopotamia sometime between ~2500 BCE and 1800 BCE. Now, to the question of how society was different before its invention? That's an incredibly interesting one, and a big part of my own research is understanding how society has changed as a result of changes in security. I do not, at the moment, have a thorough answer for you regarding the differences in society prior to and soon after, the initial invention of the pin lock. Sorry!

Credentials - I'm a Research Scholar at the Ronin Institute studying the History of Mechanical Security.

EDIT: Spelling! Sorry.

Ahoy! Thanks, /u/cudderisback for posting that! I know I'm a couple weeks late in seeing this, but I wanted to chime in with some attempts to answer the other questions!

And how did people "lock off" spaces before?

I mention briefly the existence of door seals predating the existence of the key-based lock, and again, I'm focusing purely on the middle-east/north-African origins story, but hopefully someday I'll be able to speak with some authority about the evolution of locks in Asia...anyway, door seals!

Here's a picture of one: http://imgur.com/capNgvv

"Plaques such as this were part of a door-locking system for important buildings. The plaque was embedded in the doorjamb and a peg, inserted into the central perforation, was used to hold a hook or cord that secured the door and was covered with clay impressed by one or more seals." - http://oi.uchicago.edu/collections/highlights/highlights-collection-mesopotamia

So it's easy to open these doors, just remove the peg, but in order to do that, you'd have to break the seal first and now anyone that comes upon the door in the future will know it has been breached. This method of authentication was very popular among the various peoples of Mesopotamia, and tons of personal cylinder seals have been recovered by archaeologists.

Seals were one of the more sophisticated ways of locking something up, but as the passage from U Chicago says these were "for important buildings." Think granary or the like. But, what about more personal protection. The use of locks on chests and personal dwellings came a long time after the first rudimentary locks were being placed on temple doors. Prior to that, though, people could tie complex knots that only they knew the method of untangling. The story of the Gordion Knot is a direct reference to this practice, as a matter of fact. There were even knots that offered a similar sort of security as the door seal, the most famous of which was aptly called the "thief knot". It visually resembled a common maritime knot known as the "reef" knot so if someone had rummaged through your bag (think of the situation where you've just paid someone to watch your belongings while you go about your business, you come back, everything looks alright, but they've been through your things & robbed you) they are much more likely to tie the reef knot, which the original knot maker can differentiate, alerting them to the intrusion.

Many books that attempt to tell the history of locks will make some allusion to a person rolling a boulder over a cave opening as being the first lock, but come on...I don't think I could agree with that. No mechanical cleverness or at least secret knowledge at play there. Just an obstacle, really.

Were there certain milestones in the history of locks and keys? Where there concepts and inventions that had a big impact?

Ohhhhhhh heck yes there were! I hate to punt on this, but I'm going to punt to myself and if you are very interested in the topic I'd recommend you watch these two talks:

Why do you lock your door?

and

Vulnerability research circa 1851

Here's a bit from the transcript of one of the talks, to give an idea of one of the watershed moments:

So, around the time that the lever lock was being created, around the 1770s, there was also this guy Bramah who happened to be attending when this guy Barron, who is thought of today as the inventor of the lever lock, was presenting. Bramah was attending and he saw this lever lock and he had been thinking about locks himself for quite a while.

Now, why didn't he take his ideas about the lever lock and make the detector lock that was eventually created by Chubb and is still sold today high security lever lock? Well, it's because he had a much crazier lock in mind. This is a Bramah safety lock (photo of lock). This is a vault version of the safety lock. Now, what's going on here...(description). Its actually a pretty simple idea, but really clever and advanced the art of lockmaking by...I mean, it hadn't advanced much in 1500 years, maybe more, and he just brought it into the future.

This is still sold today. Still crazy hard to pick, still used in high security applications. When he created it, there was also this funny little lock meme going around. This is Louis the 16th and Louis was an avid locksmith as well. Louis loved locks and he was trained by the master locksmith Gamain in Versaille. He and Gamain made a particular locked cabinet together called the Armoir de Fer. Now, the Armoir de Fer, made with Gamain, Louis thought was his prized and highest invention. But, they were just making warded locks, and the problem with warded locks was that as soon as you understand how it works, you don't need a key, you don't need anything, you can pick it open really easily.

So, when Louis made a safe, he inserted a bunch of secret documents in it and lost his head, because Gamain turned out to be a Jacobite, a revolutionary. And Gamain told the revolutionary council how it worked. He didn't go with them, he didn't have to open it for them. He just told them how it worked, they went, opened it up, found a bunch of treasonous documents. There were all sorts of other reasons he probably would have lost his head anyway, but that definitely contributed.

So, Bramah in England is coming out with this lock and he says "I can hand you this lock, and even thought I made it and I know exactly how it works, I can't open it. I can give you and you and you your own locks and you won't, no matter what you do to your own lock, be able to open each others."

Eventually this leads to the Great Lock Controversy of 1851 (covered in depth in the 2nd talk) which winds up being perhaps the most significant moment in the history of security, at least as fa as your own personal day-to-day security is concerned. How you behave was significantly impacted by this moment.

And was lockpicking born right when locks were invented? Or did this "art" appear at a later moment?

Lockpicking has followed pretty closely on the heels of the development of locks throughout history. It's always been an arms race, but the modern method of picking that you likely think of when you imagine a lock being picked, was probably invented sometime between 1750 and 1775. In the 19th century it was referred to as the "Tentative Method" or "tentative process" which, as best I can tell, was a reference to Issac Newton's process of scientific inquiry (or at least, I've found references to Newton's "Tentative Process" in writings that predate the discussion of the "tentative process" of picking). The idea being that trial, error and iteration apply to science as well as picking locks.

The tentative method of picking is entirely concerned with applying pressure to whatever part of the lock acts on the tumblers, then manipulating the tumblers against that pressure to determine, and place them in, their true position. In pin tumbler locks this is achieved by applying a rotating pressure to the plug of the lock, which binds the driver pins, the you press the key pins until you feel the driver pins released from that bind. In lever locks you apply a lateral pressure to the bolt, which presses it's "post" directly into the tumblers. You then pivot each tumbler as it binds against the post until you feel it go free of its bind. In disc detainer locks, you rotate the 0 disc until it applies force to the sidebar, the sidebar then presses into the other discs, you then rotate those discs until you feel them go free of their bind. In wafer locks, you again rotate the plug of the lock, binding the tabs of the wafers against the housing of the lock, you then press the wafers up or down until you feel them go free of their bind...seeing a pattern?

The tentative method - tension and manipulation - was a revolutionary discovery in the world of lockpicking, and perhaps most remarkably, it's discovery predated the majority of the locking systems it would eventually be used against. The security arms race was flipped on its ear, for 200+ years lock makers were fighting against this one technique that was readily adapted to anything they could imagine.

Alright - hope that filled in some of the blanks of my prior answer! Again, sorry I didn't see this sooner.