Main content
Computer science
Course: Computer science > Unit 2
Lesson 4: Modern cryptography- The fundamental theorem of arithmetic
- Public key cryptography: What is it?
- The discrete logarithm problem
- Diffie-hellman key exchange
- RSA encryption: Step 1
- RSA encryption: Step 2
- RSA encryption: Step 3
- Time Complexity (Exploration)
- Euler's totient function
- Euler Totient Exploration
- RSA encryption: Step 4
- What should we learn next?
© 2023 Khan AcademyTerms of usePrivacy PolicyCookie Notice
What should we learn next?
Help decide what's next! What do you want to learn? Created by Brit Cruise.
Want to join the conversation?
- I have a question for you, Brit:
How secure is public Wi-Fi? How much confidentiality you can expect when using it in some cafe?
There must be some encryption between my phone / laptop and web-site i am browsing (e.g. when logging in Facebook). But Wi-Fi point owners can have access to all the data which is going through it... or can't they?(232 votes)- WEP is like Swiss cheese...full of holes. WEP can now be broken with a standard laptop in under 10 minutes.
Almost everything about WEP was implemented very poorly. It is a really great case study demonstrating 1) why non-cryptographers shouldn't develop encryption schemes 2) why it is a really good idea to publish your encryption schemes (Much better to have a friendly cryptographer break your scheme and tell you your scheme has problems, than keep it secret, and think it is secure while a criminal breaks it and doesn't tell you) This is the one thing they got right with WEP.
WPA fixed some things with WEP, but the community is poking holes in it too. The community has broken WPA-TKIP in under 20 minutes now.
WPA with AES appears to be okay for now, but many people are not using it (many people have older routers that don't support it ).(230 votes)
- How does the encryption/decryption for DVDs and Blue Rays work ?(294 votes)
- Vote up Camerons question if interested in Advanced Access Content System (http://en.wikipedia.org/wiki/Advanced_Access_Content_System). Good idea!
In the meantime, this is a really interesting excerpt from an article I read on this subject - Interesting how time sensitivity plays a role in the studios strategy:
Since some of you might now be gearing up to buy a Blu-ray player, here's how it works. Studios will hire software developers to encrypt their latest releases. Someday, hackers will find a flaw, crack the encryption and post the movie on the Internet. Once the movie is out in the wild "there is no way to make it unplayable," Kocher said. "You can't put the genie back in the bottle."
The studios, however, are banking on the idea that it might take months to crack a particular encryption scheme. By that time, the studios will have hoped that they have already pulled in the bulk of the revenue from that movie or title.
"Their business model is to make money in the first few weeks of release," he said.
That doesn't work with "Lawrence of Arabia." Film fans will likely be renting or buying that for years, so the studios will lose money on future sales.
But "Harold and Kumar Escape from Guantanamo Bay" or "Predator versus Alien versus Martin Lawrence as Big Momma"? How many people will be renting those movies three months after the initial release date on Blu-ray? I mean, other than film students writing a thesis? It's not like were talking about "Die Hard with a Vengeance" here.
Think of it. Go to your local video store and look in the section where they keep the movies from the 80s. When was the last time you had a burning desire to see "Ladyhawke?" It's like visiting a refugee camp.
Once a given encryption scheme is cracked, the studios then can shift to a new encryption scheme to start the cycle all over again. Hackers could try to break Blu-ray by creating a virtual copy of the hardware and thus fool the encryption on the disks, but that will be tough. "A Blu-ray player is a complicated piece of hardware," he said.
"(92 votes)
- Just Curious: What is Quantum Cryptography? Is it just using a specific atoms quantum state to get a seed for a pseudorandom number, or is it something completely different? If it's different, could you please explain what it is?(125 votes)
- There are different ways of quantum encryption: quantum entanglement for example, and each works differently.
I was first introduced to the BB84 protocol, what I am about to explain below (in a nutshell). In normal classical encryption, you can't detect whether Eve's listening to your message. However, in quantum encryption, you can detect it. There is more to it, and that require Brit Cruise and his team to enlighten us.(52 votes)
- Hi brit i was wondering when will some new videos be put up. I really enjoy watching your videos so I go to khan academy every hour just to see if you have a new video put up.(39 votes)
- New series on Information Theory can be found here:
http://www.khanacademy.org/math/applied-math/info-theory(87 votes)
- How does one prevent Man in the Middle attacks?(56 votes)
- +wariolandgoldpiramid that's what a MITM (Man In The Middle) attack is.
For example; say you have a wireless network called "strong_net". What you aren't seeing searching for wireless networks however is that there are multiple access points to this network, and the computer will just pick the strongest one.
If I set up a computer network which mimics this network (i.e. same name), your computer will connect to my network instead (without you knowing). Now I can transparently reroute your traffic through my computer and onto the internet. When you log into a site, I can read your information.
MITM attacks, then, is more of a computer science question, not so much a cryptography question. Cryptography assumes a MITM attack, but the middle man cannot read the information anyway (I'd be Eve!).
Also, the Sony breach is not a MITM attack, but an attack called "SQL injection". This is already turning into a wall of text, so I'm not explaining it right here, but you can search for it.(28 votes)
- An understandable intro to hashes is sorely needed, I haven't found much help elsewhere on the internet. Also, a discussion of key sizes and why DES has given way to AES and Twofish would be another great advanced lesson.(42 votes)
- I agree. I didn't explicitly mention them yet, though we can easily define them now since random mapping has been introduced. I'll definitely start with hash functions before getting into block ciphers and substitution permutation networks(24 votes)
- Hi Brit, I was wondering how the cryptography changes as the computers get faster and faster, primarily I am thinking about quantum computers here - how do they affect the current encryption and which kind of new encryption are considered? Is there something entirely new coming or is it just a "expansion" of the currently working?(31 votes)
- As regular computers get faster we can simply increase the size of the encryption keys. Quantum computers, however, are able to solve many of the difficult computational problems underlying cryptographic systems much faster (technically, in the RSA cryptosystem a regular computer would need an amount of time that is exponential in the size of the key in order to factor it into prime numbers, while a quantum computer can do it in polynomial time using Shor's algorithm.)
However, the laws of quantum mechanics also allow for a new kind of quantum cryptography. This works by encoding each bit of a message we want to transmit as a qubit, a quantum bit. Roughly speaking, instead of storing simply a zero or a one like a regular bit, it can store an arbitrary superposition of the state zero and the state one. Think of this as a sort of angle. For example, Alice and Bob can agree that an angle of X degrees represents a zero, while an angle of X + 90 degrees represents a one. Measuring the qubit at X degrees will then give us a zero if the qubit was in the X state and a one if the qubit was in the X + 90 degrees states. However if we measure at X + 45 degrees, we have a 50% chance of getting a zero and a 50% chance of getting one. The result is that an eavesdropper Eve is unable to intercept the message if she doesn't know the angle X that Alice and Bob agreed on. Another interesting effect of quantum mechanics is that measuring a qubit changes its state. Alice and Bob are thus able to detect that Eve is trying to eavesdrop on them.(35 votes)
- Could you tell us more about encryption, computer security, etc? I think it would be great if we could learn about how an antivirus program, say AVG, works to find and destroy viruses. You could even tell us how the cookies that keep us logged in on Khan Academy work.
Thanks,
Matthew(30 votes)- I agree virus/antivirus battles would be a fascinating lesson, great idea. I'm going to do some lessons on practical computer encryption first (such as DES and AES)..though I'll keep thinking about this(23 votes)
- This series really paid off with the Diffie Helman and the RSA videos! I've never seen a more comprehensible explanation that starts to get into the nitty gritty of the algorithms.
How does signing work? Specifically, what do the decryption algorithms do to allow Alice to verify Bob's message wasn't altered by Eve? What's the difference between signing a message and signing a key... algorithmically? I don't expect answers in this forum, but those were the things on my mind as I finished this trail. Great work, Britt!(22 votes)- Dear Sir/Madam,
i want to distribute key with multiple party in secure manner so which method will be good(1 vote)
- I would enjoy listening to something on bits of entropy and how it relates to password strength. Also, on some of the attacks used to break or weaken cyphers.(20 votes)
- Entropy will be fleshed out in the next series on Information Theory - stay tuned. In short: a password which is chosen at random is strongest, period. This is because it's equally likely to be anything. Entropy is a measure of uncertainty (expressed in bits), so we would say higher entropy = stronger password.
I agree attacks should be be explored. We just need to decide what kind of attacks we look at first. Please vote up stanelburger's question on man in the middle so we can help set priority.(11 votes)
Video transcript
You've reached the first
checkpoint in the Journey to Cryptography series. And now I want to
talk about what's next, because I'm
working on a new series. However, this one
won't end here. And if anything, we're kind
of at the beginning still. So I'm going to do three
different checkpoint videos. This one is on advanced lessons. However, I also want
to eventually talk about tasks and
challenges and what we can do with more interactive
explorations and computer science lessons as it
applies to cryptography. But for now, let's talk
about advanced lessons. And when I say advanced,
I don't necessarily mean harder lessons. I mean more detailed. And let me give you a
conceptual idea for what I think this series could be,
and future series. I like to think of each series
as the trunk of a tree, where I took you from
prehistoric times to around the 20th
century, which is here, with a few different threads. And these ideas kind
of branch apart. Once you hit the 20th
and 21st century, they start getting
highly specific. And way down here on the leaves
are current research questions, which over here might
be problems related to prime number distribution,
and over here some very specific work being done
on randomized algorithms or hash functions. And, say, up here, we might
have new public key protocols because RSA was just the first. Or we also have encryption
standards such as DES and AES. We would have a whole new
branch on quantum cryptography. So as you can see, there's
so many different things that branch out of this series. And I couldn't possibly
do justice to them all. So I think of this video
as living right here. It's kind of a junction point. Now I could branch
off with the help of the community and
possibly other video creators to fill out this tree gradually
over time, specifically with the help of the community. And I'm really excited about the
question and answer community and the work being done
to improve how people can help people on Khan Academy. So for example, in terms of
where one of these branches can go, I've noticed
clusters of questions kind of leading into a common branch. For example, under the
pseudo-random number generator-- I have two
questions here, one by Sonnie and one by Drakain. Drakain's question
is, "Why has he suggested that time
in milliseconds is a suitable random seed? This is a huge
no-no in security. The time it is on your
machine is the time is on my machine, give
or take 100 milliseconds, which can be brute
force attacked." And again, this is a
great question, too, because it speaks to the
need that I didn't present a cryptographically secure
pseudo-random generator. So the middle squares
method is back here in the early 20th century. But up till today, we are
not using the middle squares method. And that's a whole
interesting branch. And it's these sort
of questions which cluster together and
really drive new content. And I want to show you a
really interesting example of how this has
happened already. This is a question Samuel asked
on the One-Time Pad video. He said, "Wouldn't a computer be
able to test all possibilities very fast?" And Chumpatrol basically
asked the same question here. I see this happening a
lot, similar questions. All speak to the
need of a new video. So I went and created a video
on perfect secrecy, which really nails down how you
can't beat randomness in the world of encryption. And out of this video, Dawn
made a really great comment. And what they did was
basically summarize my video in two sentences. So this is what I want to try
to do more of in filling out these branches-- take
questions, make new content, and have this kind of feedback
loop, and see what we can do. So now what I would
really love is for you to ask questions
below this video, which arise after watching
the entire series. So not specific details
about certain videos, those can go with the videos. But new questions,
which are kind of opening a new can of worms. And what I think
will be fun to do is your question
will lead to answers by both me and the
rest of the community. So we'll have multiple answers. And what I can do is take
this body of answers, and out of this, draft
up a rough script for more advanced videos
on specific topics that subsets of the
community care about. So hopefully out
of the discussion below, over time we can
grow a bunch of new videos. And I want to be clear. This is an ongoing process. So this won't happen
tomorrow or next week. I hope it can happen months
and even years from now. We can still be building out
new videos off this series, and these videos can be
a collaborative effort between myself and the community
and perhaps other video creators down the road. So let me know what you think
below and let's get started.