Public Keys, One Way Functions and Hard Problems

545 Download(s)

Lesson synopsis

Public KeySecurity has always been a major focus of computer science research, and with the explosion of Internet use by commerce, the need for secure transactions has taken on more urgency. Most recently, cyber-thieves demonstrated that true security on the Internet is going to require a new level of understanding of how to protect personal data, and more importantly, financial transactions. This lesson introduces two important concepts: public key encryption and one-way functions. It provides an opportunity for students to understand the underpinnings of almost all Internet security: they will come to appreciate that any lock can be eventually broken, and that theoretical computer scientists study ‘hard’ problems to lengthen the time it will take to break a lock. Note that this is not a lesson in encryption, but in how mathematics is used to secure information.

Age Levels

11 - 14 years

Objectives

Introduce students to:
The concept of a public key
How the modulo function is a one-way function
How the Diffie-Hellman key exchange uses a one-way function
What computer scientists mean by ‘hard’ problems

Anticipated learner outcomes

Students will be able to
Practice creating public keys with the classic color model.
Exchange information with the Diffie-Hellman method using modulo arithmetic.
Explain why no lock can be completely secured, and that given time, any mathematical ‘lock’ can be broken.
Use exponentiation and modulo arithmetic to create cyber-keys.
Router
Sandra Lerner

It is difficult to imagine a time when computers were not capable of sharing information and resources with great ease. Sandra Lerner pushed the boundaries of network computing as one of the co-founders of Cisco Systems, which introduced one of the first commercially viable routers. The router was born while Sandra was working at Stanford University in the 1980’s after earning her Master’s degree there in Computer Science. To avoid the tedious task of transferring information between computers using floppy disks, she and co-founder of Cisco, Leonard Bosack, created a local area network, or LAN, between their campus offices using a multiprotocol router that Bosack developed. Shortly thereafter the pair started Cisco Systems, and began selling the router which was a success, because it could work with so many different types of computers. After Leaving Cisco in 1990, Lerner started the trendy cosmetics company Urban Decay and became a philanthropist and avid activist for animal rights.

CGA palette
Mark Dean

If you have ever used a PC with a color display you have been acquainted with the work of Mark Dean. After achieving a Bachelor’s degree in electrical engineering from the University of Tennessee, Dean began his career at IBM. Dean served as the chief engineer on the team that developed the first IBM PC, for which he currently holds one third of the patents. With colleague Dennis Moeller, he developed the Industry Standard Architecture (ISA) systems bus, which enabled peripheral devices such as printers, keyboards, and modems to be directly connected to computers, making them both affordable and practical. He also developed the Color Graphics Adapter which allowed for color display on the PC. Most recently, Dean spearheaded the team that developed the one-gigahertz processor chip. Dean went on to obtain a MSEE from Florida Atlantic University and a Ph.D. in electrical engineering from Stanford University. He is a member of the National Academy of Engineering, has been inducted into the National Inventors Hall of Fame, and is the first African-American IBM Fellow.

Bletchley Park
Dr. Sue Black
Dr. Sue Black

Dr. Sue Black has demonstrated the power of social networking. She used Web 2.0 technologies to help raise awareness of, and critical funding for, Bletchley Park, the UK World War II center for decrypting enemy messages. She has also been an active campaigner for equality and support for women in technology fields, founding a number of online networking platforms for women technology professionals. A keen researcher, Dr. Black completed a PhD in software measurement in 2001. Her research interests focus on software quality improvements. She has recently won the PepsiCo Women's Inspiration Network award, been named Tech Hero by ITPRO magazine and was awarded the first John Ivinson Award from the British Computer Society. In 2011 Dr. Black set up The goto Foundation, a nonprofit organization which aims to make computer science more meaningful to the public, generate public excitement in the creation of software, and build a tech savvy workforce. Read Sue's blog about The goto Foundation: http://gotofdn.org

Liz Gerber - Image credit Lisa Beth Anderson
Liz Gerber
Liz Gerber - Image credit Lisa Beth Anderson

Liz Gerber earned her MS and PhD in Product Design and Management Science and Engineering at Stanford. She specializes in design and human-computer interaction, particularly how social computing supports the innovation process. Her current research investigates crowd-funding as a mechanism for reducing disparities in entrepreneurship.
Gerber's work funded by the US National Science Foundation and the National Collegiate Inventors and Innovators Alliance has appeared in peer-reviewed journals, including Transactions on Computer Human Interactions, Design Studies, and Organization Science.
As an award-winning teacher and researcher, Liz has touched the lives of more than 6,000 students through her teaching at Northwestern's Segal Design Institute and Stanford University's Hasso Plattner's Institute of Design and through her paradigm-shifting creation, Design for America, a national network of students using design to tackle social challenges.

Image credit - Lisa Beth Anderson

Turing machine
Alan Mathison Turing
Alan Mathison Turing

Did you know that computing has been used in military espionage and has even influenced the outcome of major wars? Alan Mathison Turing designed the code breaking machine that enabled the deciphering of German communications during WWII. As per the words of Winston Churchill, this would remain the single largest contribution to victory. In addition, he laid the groundwork for visionary fields such as automatic computing engines, artificial intelligence and morphogenesis. Despite his influential work in the field of computing, Turing experienced extreme prejudice during his lifetime regarding his sexual orientation. There is no doubt that computers are ubiquitously part of our lives due to the infusion of Turing’s contributions.

Image credits