You are browsing as Guest
Click here for list of discussions
Click here to login





Discussion: CryptographyFoundations
You have read-only access
You may need to scroll to the right ...

Click here to view in strict time order
Click here to view in neighbourhood mode.

%3 N_20250328093925f_ColinWright    By ColinWright 2025/03/28 @ 09:39:25f -------------------------------- Sometimes a function can be specific by a formula, but sometimes not        (select only this node)     N_20250328094139a_ColinWright    By ColinWright 2025/03/28 @ 09:41:39a -------------------------------- We have functions that carry symbols and glyphs to numbers, and other functions that carry numbers to glyphs. As a result we can restrict our attention to dealing with whichever is convenient at the time.        (select only this node)     N_20250328093925f_ColinWright->N_20250328094139a_ColinWright N_20250328094258a_ColinWright    By ColinWright 2025/03/28 @ 09:42:58a -------------------------------- Sometimes a function is specified by a process one performs on the input, generating the output.        (select only this node)     N_20250328093925f_ColinWright->N_20250328094258a_ColinWright N_20250328093925g_ColinWright    By ColinWright 2025/03/28 @ 09:39:25g -------------------------------- It's best to think of a function like this: Blob of things over to the left, Blob of things over to the right, a function points from each of the things from the blob on the left to something in the blob on the right.        (select only this node)     N_20250328093925f_ColinWright->N_20250328093925g_ColinWright N_20250328093925b_ColinWright    By ColinWright 2025/03/28 @ 09:39:25b -------------------------------- (Though no doubt there will be things missing to start with!)        (select only this node)     N_20250328093925c_ColinWright    By ColinWright 2025/03/28 @ 09:39:25c -------------------------------- We start with some very basic definitions        (select only this node)     N_20250328093925d_ColinWright    By ColinWright 2025/03/28 @ 09:39:25d -------------------------------- A "Function" is a thing that takes something as an input and produces something as an output        (select only this node)     N_20250328093925c_ColinWright->N_20250328093925d_ColinWright N_20250328093925d_ColinWright->N_20250328093925f_ColinWright N_20250328093925e_ColinWright    By ColinWright 2025/03/28 @ 09:39:25e -------------------------------- This sounds too generic to be useful, but it's a starting point.        (select only this node)     N_20250328093925d_ColinWright->N_20250328093925e_ColinWright N_20250328095443a_ColinWright    By ColinWright 2025/03/28 @ 09:54:43a -------------------------------- Sometimes a function can take more than one "thing" to create its output, such as f(x,y)=x^2+y^2 ... but in these cases we think of the *pair* of things as the input, so the input is the *pair* (x,y), not x and y separately.        (select only this node)     N_20250328093925d_ColinWright->N_20250328095443a_ColinWright N_20250328103614a_ColinWright    By ColinWright 2025/03/28 @ 10:36:14a -------------------------------- https://en.wikipedia.org/wiki/Function_%28mathematics%29        (select only this node)     N_20250328093925e_ColinWright->N_20250328103614a_ColinWright N_20250328094354a_ColinWright    By ColinWright 2025/03/28 @ 09:43:54a -------------------------------- Note that the blobs need not contain the same types of things. One might contain numbers, another might contain glyphs, and yet another might contain, for example, sounds.        (select only this node)     N_20250328093925g_ColinWright->N_20250328094354a_ColinWright N_20250328095804a_ColinWright    By ColinWright 2025/03/28 @ 09:58:04a -------------------------------- So we have the concept of a function. Here are some examples:        (select only this node)     N_20250328094258a_ColinWright->N_20250328095804a_ColinWright N_20250328095538a_ColinWright    By ColinWright 2025/03/28 @ 09:55:38a -------------------------------- By using this technical trick we can think of functions as taking a single "thing" as input and producing a single "thing" as output.        (select only this node)     N_20250328095443a_ColinWright->N_20250328095538a_ColinWright N_20250328095804e_ColinWright    By ColinWright 2025/03/28 @ 09:58:04e -------------------------------- Converting the spreadsheet you see to a CSV file        (select only this node)     N_20250328095804a_ColinWright->N_20250328095804e_ColinWright N_20250328095804c_ColinWright    By ColinWright 2025/03/28 @ 09:58:04c -------------------------------- Converting a letter you type to a number stored in memory on the computer.        (select only this node)     N_20250328095804a_ColinWright->N_20250328095804c_ColinWright N_20250328095804b_ColinWright    By ColinWright 2025/03/28 @ 09:58:04b -------------------------------- f(x)=x^2-x-1        (select only this node)     N_20250328095804a_ColinWright->N_20250328095804b_ColinWright N_20250328095804d_ColinWright    By ColinWright 2025/03/28 @ 09:58:04d -------------------------------- Converting an HTML document to a PDF document        (select only this node)     N_20250328095804a_ColinWright->N_20250328095804d_ColinWright N_20250328100816a_ColinWright    By ColinWright 2025/03/28 @ 10:08:16a -------------------------------- A "Hash function" takes an arbitrary input and produces a fixed-size output.        (select only this node)     N_20250328100816b_ColinWright    By ColinWright 2025/03/28 @ 10:08:16b -------------------------------- Related concepts:        (select only this node)     N_20250328100816a_ColinWright->N_20250328100816b_ColinWright N_20250328101537a_ColinWright    By ColinWright 2025/03/28 @ 10:15:37a -------------------------------- A good hash function has the property that for a random input, each bit in the output has a 50:50 chance of being a "1".        (select only this node)     N_20250328100816a_ColinWright->N_20250328101537a_ColinWright N_20250328100213a_ColinWright    By ColinWright 2025/03/28 @ 10:02:13a -------------------------------- There are also several classes of function that are of particular interest in cryptography.        (select only this node)     N_20250328095804b_ColinWright->N_20250328100213a_ColinWright N_20250328095804c_ColinWright->N_20250328100213a_ColinWright N_20250328095804d_ColinWright->N_20250328100213a_ColinWright N_20250328095804e_ColinWright->N_20250328100213a_ColinWright N_20250328100213c_ColinWright    By ColinWright 2025/03/28 @ 10:02:13c -------------------------------- Encryption        (select only this node)     N_20250328100213a_ColinWright->N_20250328100213c_ColinWright N_20250328100213d_ColinWright    By ColinWright 2025/03/28 @ 10:02:13d -------------------------------- Decryption        (select only this node)     N_20250328100213a_ColinWright->N_20250328100213d_ColinWright N_20250328100213b_ColinWright    By ColinWright 2025/03/28 @ 10:02:13b -------------------------------- Hash function        (select only this node)     N_20250328100213a_ColinWright->N_20250328100213b_ColinWright N_20250328100213e_ColinWright    By ColinWright 2025/03/28 @ 10:02:13e -------------------------------- Signing        (select only this node)     N_20250328100213a_ColinWright->N_20250328100213e_ColinWright N_20250328103650a_ColinWright    By ColinWright 2025/03/28 @ 10:36:50a -------------------------------- https://en.wikipedia.org/wiki/Hash_function        (select only this node)     N_20250328100213b_ColinWright->N_20250328103650a_ColinWright N_20250328100213b_ColinWright->N_20250328100816a_ColinWright N_20250328121037a_ColinWright    By ColinWright 2025/03/28 @ 12:10:37a -------------------------------- Take a message and a key and produce an output that looks random and (in theory) can only be decrypted and read by specific intended reqipients.        (select only this node)     N_20250328100213c_ColinWright->N_20250328121037a_ColinWright N_20250328121256a_ColinWright    By ColinWright 2025/03/28 @ 12:12:56a -------------------------------- Take an encrypted message (the output from an encryption process) and a key and reproduce the original message.        (select only this node)     N_20250328100213d_ColinWright->N_20250328121256a_ColinWright N_20250328123950a_ColinWright    By ColinWright 2025/03/28 @ 12:39:50a -------------------------------- Once you've received a message, you need a way to know who it's from. Remember ... Don't Trust Anyone! Just because they say it's someone, it doesn't mean it is.        (select only this node)     N_20250328100213e_ColinWright->N_20250328123950a_ColinWright N_20250328100816g_ColinWright    By ColinWright 2025/03/28 @ 10:08:16g -------------------------------- There are more        (select only this node)     N_20250328100816d_ColinWright    By ColinWright 2025/03/28 @ 10:08:16d -------------------------------- check digit        (select only this node)     N_20250328100816b_ColinWright->N_20250328100816d_ColinWright N_20250328100816e_ColinWright    By ColinWright 2025/03/28 @ 10:08:16e -------------------------------- fingerprint        (select only this node)     N_20250328100816b_ColinWright->N_20250328100816e_ColinWright N_20250328100816c_ColinWright    By ColinWright 2025/03/28 @ 10:08:16c -------------------------------- checksum        (select only this node)     N_20250328100816b_ColinWright->N_20250328100816c_ColinWright N_20250328100816f_ColinWright    By ColinWright 2025/03/28 @ 10:08:16f -------------------------------- These can all be thought of as hash functions with specific characteristics        (select only this node)     N_20250328100816c_ColinWright->N_20250328100816f_ColinWright N_20250328100816d_ColinWright->N_20250328100816f_ColinWright N_20250328100816e_ColinWright->N_20250328100816f_ColinWright N_20250328100816f_ColinWright->N_20250328100816g_ColinWright N_20250328101537b_ColinWright    By ColinWright 2025/03/28 @ 10:15:37b -------------------------------- (This means the hash value can be used as a representative of the input)        (select only this node)     N_20250328101537c_ColinWright    By ColinWright 2025/03/28 @ 10:15:37c -------------------------------- Beyond this, for cryptography we want additional properties:        (select only this node)     N_20250328101537a_ColinWright->N_20250328101537c_ColinWright N_20250328101537a_ColinWright->N_20250328101537b_ColinWright N_20250328101537e_ColinWright    By ColinWright 2025/03/28 @ 10:15:37e -------------------------------- Finding a second input that matches the given hash value when one input is already known is infeasible        (select only this node)     N_20250328101803a_ColinWright    By ColinWright 2025/03/28 @ 10:18:03a -------------------------------- These are all "clearly related", but when you start doing deep analysis of hash functions it turns out that there are subtle differences.        (select only this node)     N_20250328101537e_ColinWright->N_20250328101803a_ColinWright N_20250328101537g_ColinWright    By ColinWright 2025/03/28 @ 10:15:37g -------------------------------- This is called a "Collision"        (select only this node)     N_20250328101537e_ColinWright->N_20250328101537g_ColinWright N_20250328101537d_ColinWright    By ColinWright 2025/03/28 @ 10:15:37d -------------------------------- Finding an input string that matches a given hash value (a pre-image) is infeasible        (select only this node)     N_20250328101537c_ColinWright->N_20250328101537d_ColinWright N_20250328101537f_ColinWright    By ColinWright 2025/03/28 @ 10:15:37f -------------------------------- It is infeasible to find *any* pair of different inputs that yield the same hash value.        (select only this node)     N_20250328101537c_ColinWright->N_20250328101537f_ColinWright N_20250328101537c_ColinWright->N_20250328101537e_ColinWright N_20250328101537d_ColinWright->N_20250328101803a_ColinWright N_20250328101537f_ColinWright->N_20250328101803a_ColinWright N_20250328101537h_ColinWright    By ColinWright 2025/03/28 @ 10:15:37h -------------------------------- Finding a collision is related to the so-called Birthday Paradox        (select only this node)     N_20250328101537g_ColinWright->N_20250328101537h_ColinWright N_20250328101912a_ColinWright    By ColinWright 2025/03/28 @ 10:19:12a -------------------------------- Hash functions that have these (and other) properties are, for perhaps obvious reasons, called "Cryptographc Hash Functions" (CHFs).        (select only this node)     N_20250328101803a_ColinWright->N_20250328101912a_ColinWright N_20250328103737a_ColinWright    By ColinWright 2025/03/28 @ 10:37:37a -------------------------------- https://en.wikipedia.org/wiki/Cryptographic_hash_function        (select only this node)     N_20250328101912a_ColinWright->N_20250328103737a_ColinWright N_20250328104158a_ColinWright    By ColinWright 2025/03/28 @ 10:41:58a -------------------------------- One use for a CHF is a technique for checking passwords.        (select only this node)     N_20250328101912a_ColinWright->N_20250328104158a_ColinWright N_20250328104158b_ColinWright    By ColinWright 2025/03/28 @ 10:41:58b -------------------------------- So a user wants to access a system and has a password. But we don't want to store the (Username,Password) pair.        (select only this node)     N_20250328104158a_ColinWright->N_20250328104158b_ColinWright N_20250328104158c_ColinWright    By ColinWright 2025/03/28 @ 10:41:58c -------------------------------- (If the file containing that data gets leaked, then anyone in possession of it could pretend to be anyone)        (select only this node)     N_20250328104158b_ColinWright->N_20250328104158c_ColinWright N_20250328104158d_ColinWright    By ColinWright 2025/03/28 @ 10:41:58d -------------------------------- So instead we have a CHF, apply that to the password, and store that with the username        (select only this node)     N_20250328104158b_ColinWright->N_20250328104158d_ColinWright N_20250328104326a_ColinWright    By ColinWright 2025/03/28 @ 10:43:26a -------------------------------- Now if the password file is compromised, any attacker doesn't know the password, so they can't login as a user.        (select only this node)     N_20250328104158c_ColinWright->N_20250328104326a_ColinWright N_20250328104158d_ColinWright->N_20250328104326a_ColinWright N_20250328104158e_ColinWright    By ColinWright 2025/03/28 @ 10:41:58e -------------------------------- When a user tries to login we hash the password they give us and compare that against the stored hash        (select only this node)     N_20250328104158d_ColinWright->N_20250328104158e_ColinWright N_20250328104158f_ColinWright    By ColinWright 2025/03/28 @ 10:41:58f -------------------------------- If it doesn't match then they definitely don't have the right password        (select only this node)     N_20250328104158e_ColinWright->N_20250328104158f_ColinWright N_20250328104158g_ColinWright    By ColinWright 2025/03/28 @ 10:41:58g -------------------------------- If it matches then they almost certainly have the right password        (select only this node)     N_20250328104158e_ColinWright->N_20250328104158g_ColinWright N_20250328104713a_ColinWright    By ColinWright 2025/03/28 @ 10:47:13a -------------------------------- This "almost" is what then dictates how big the hash should be to avoid collisions to some level of probability.        (select only this node)     N_20250328104158g_ColinWright->N_20250328104713a_ColinWright N_20250328104326b_ColinWright    By ColinWright 2025/03/28 @ 10:43:26b -------------------------------- Unless ...        (select only this node)     N_20250328104326a_ColinWright->N_20250328104326b_ColinWright N_20250328104811a_ColinWright    By ColinWright 2025/03/28 @ 10:48:11a -------------------------------- Suppose a user uses a common dictionary word as a password. An attacker can run every word in the dictionary through the hash function and see if the hash matches any entries in the password file.        (select only this node)     N_20250328104326b_ColinWright->N_20250328104811a_ColinWright N_20250328104811b_ColinWright    By ColinWright 2025/03/28 @ 10:48:11b -------------------------------- (We have to assume the attacker knows the CHF used to store the passwords)        (select only this node)     N_20250328104811a_ColinWright->N_20250328104811b_ColinWright N_20250328104811c_ColinWright    By ColinWright 2025/03/28 @ 10:48:11c -------------------------------- So the user can change: "s" to "5", "h" to "4", ... and so on        (select only this node)     N_20250328104811a_ColinWright->N_20250328104811c_ColinWright N_20250328105024a_ColinWright    By ColinWright 2025/03/28 @ 10:50:24a -------------------------------- So the person *storing* the hash of the passwords doesn't simply hash the password. They pre-pend a string called the "Salt" to the password, then hash that.        (select only this node)     N_20250328104811b_ColinWright->N_20250328105024a_ColinWright N_20250328104811d_ColinWright    By ColinWright 2025/03/28 @ 10:48:11d -------------------------------- But the attacker can try doing that to every dictionary entry        (select only this node)     N_20250328104811c_ColinWright->N_20250328104811d_ColinWright N_20250328105708a_ColinWright    By ColinWright 2025/03/28 @ 10:57:08a -------------------------------- To thwart the attacker and prevent them simply from trying every possibly version of every dictionary word, with the salt, we now ask for an extra property of the CHF ...        (select only this node)     N_20250328104811d_ColinWright->N_20250328105708a_ColinWright N_20250328104811f_ColinWright    By ColinWright 2025/03/28 @ 10:48:11f -------------------------------- What's more, the attacker might have done this *in advance*        (select only this node)     N_20250328104811d_ColinWright->N_20250328104811f_ColinWright N_20250328104811e_ColinWright    By ColinWright 2025/03/28 @ 10:48:11e -------------------------------- (Computers are *very* fast these days)        (select only this node)     N_20250328104811d_ColinWright->N_20250328104811e_ColinWright N_20250328104811e_ColinWright->N_20250328105708a_ColinWright N_20250328104811f_ColinWright->N_20250328105024a_ColinWright N_20250328105024b_ColinWright    By ColinWright 2025/03/28 @ 10:50:24b -------------------------------- Confirming that the user knows the password still works, but any pre-computation has to be specific to the system being attacked, as it will depend on the salt used by that system.        (select only this node)     N_20250328105024a_ColinWright->N_20250328105024b_ColinWright N_20250328105024a_ColinWright->N_20250328105708a_ColinWright N_20250328105708b_ColinWright    By ColinWright 2025/03/28 @ 10:57:08b -------------------------------- We ask that it be fundamentally slow to compute.        (select only this node)     N_20250328105708a_ColinWright->N_20250328105708b_ColinWright N_20250328105708d_ColinWright    By ColinWright 2025/03/28 @ 10:57:08d -------------------------------- When we design a hash function for storing hashes of passwords, we design it to be slow        (select only this node)     N_20250328105708b_ColinWright->N_20250328105708d_ColinWright N_20250328105708c_ColinWright    By ColinWright 2025/03/28 @ 10:57:08c -------------------------------- When we are using hashes to detect possible file duplications, we need to use the hash function a lot, so some hashes functions are designed to be blindingly fast.        (select only this node)     N_20250328105708b_ColinWright->N_20250328105708c_ColinWright N_20250328105808a_ColinWright    By ColinWright 2025/03/28 @ 10:58:08a -------------------------------- An example is the "SHA" family        (select only this node)     N_20250328105708c_ColinWright->N_20250328105808a_ColinWright N_20250328110019a_ColinWright    By ColinWright 2025/03/28 @ 11:00:19a -------------------------------- See the Password hashing section here: https://en.wikipedia.org/wiki/Key_derivation_function        (select only this node)     N_20250328105708d_ColinWright->N_20250328110019a_ColinWright N_20250328105708e_ColinWright    By ColinWright 2025/03/28 @ 10:57:08e -------------------------------- An example is "bcrypt"        (select only this node)     N_20250328105708d_ColinWright->N_20250328105708e_ColinWright N_20250328112012a_ColinWright    By ColinWright 2025/03/28 @ 11:20:12a -------------------------------- Some nodes are selected. Click on a node to toggle it. Initially only selected nodes and their neighbours are shown.        (select only this node)     N_20250331125336a_ColinWright    By ColinWright 2025/03/31 @ 12:53:36a -------------------------------- Click in the interior of the top node to see it in action.        (select only this node)     N_20250328112012a_ColinWright->N_20250331125336a_ColinWright N_20250331125054a_ColinWright    By ColinWright 2025/03/31 @ 12:50:54a -------------------------------- There is a link to switch out of "neighbourhood Mode" so you can then see the entire network.        (select only this node)     N_20250328112012a_ColinWright->N_20250331125054a_ColinWright N_20250328121037a_ColinWright->N_20250328121256a_ColinWright N_20250328093925a_ColinWright    By ColinWright 2025/03/28 @ 09:39:25a -------------------------------- Basic ideas underlying modern cryptography, starting right from the ground up        (select only this node)     N_20250328093925a_ColinWright->N_20250328093925b_ColinWright N_20250328093925a_ColinWright->N_20250328093925c_ColinWright N_20250328093925a_ColinWright->N_20250328112012a_ColinWright N_20250328121256b_ColinWright    By ColinWright 2025/03/28 @ 12:12:56b -------------------------------- Note that the encryption and decryption keys might be different        (select only this node)     N_20250328121256a_ColinWright->N_20250328121256b_ColinWright N_20250328121256a_ColinWright->N_20250328123950a_ColinWright N_20250328121256c_ColinWright    By ColinWright 2025/03/28 @ 12:12:56c -------------------------------- They are the same in Symmetric Ciphers        (select only this node)     N_20250328121256b_ColinWright->N_20250328121256c_ColinWright N_20250328121256d_ColinWright    By ColinWright 2025/03/28 @ 12:12:56d -------------------------------- They are different in Asymmetric Ciphers        (select only this node)     N_20250328121256b_ColinWright->N_20250328121256d_ColinWright N_20250328121256e_ColinWright    By ColinWright 2025/03/28 @ 12:12:56e -------------------------------- Also known as "Public Key Ciphers"        (select only this node)     N_20250328121604a_ColinWright    By ColinWright 2025/03/28 @ 12:16:04a -------------------------------- The idea here is that since the encryption and decryption keys are different, you can publish the encryption key, the so-called "Public Key", and keep the decryption key secret, the so-called "Private Key"        (select only this node)     N_20250328121256e_ColinWright->N_20250328121604a_ColinWright N_20250328123950b_ColinWright    By ColinWright 2025/03/28 @ 12:39:50b -------------------------------- But using Public Key Encryption techniques we can know that a message is from a given person. Do do this they "Sign" the message.        (select only this node)     N_20250328123950a_ColinWright->N_20250328123950b_ColinWright N_20250328121256d_ColinWright->N_20250328121256e_ColinWright N_20250328121604b_ColinWright    By ColinWright 2025/03/28 @ 12:16:04b -------------------------------- Then anyone can use the public key to encrypt a message and send it to you, but only you can read the message.        (select only this node)     N_20250328121604a_ColinWright->N_20250328121604b_ColinWright N_20250328121604c_ColinWright    By ColinWright 2025/03/28 @ 12:16:04c -------------------------------- (assuming the system isn't broken)        (select only this node)     N_20250328121604b_ColinWright->N_20250328121604c_ColinWright N_20250328121604b_ColinWright->N_20250328123950a_ColinWright