מערכות הצפנה המבוססות על מפתחות ציבוריים הומצאו בשנות ה- 70 המאוחרות של המאה הקודמת, עם קצת עזרה מהתפתחות תורת המספרים המרוכבים שארעה בערך באותו זמן. נבחן אז הרעיון שניתן יהיה לפתח מערכת הצפנה אשר יהיו לה שני מפתחות, מפתח סודי ומפתח ציבורי. עם המפתח הציבורי ניתן יהיה להצפין הודעות, אשר ניתן יהיה לפענח אותן עם המפתח הפרטי. כך הבעלים של המפתח הפרטי יהיה היחיד אשר יוכל לפענח את ההודעות המוצפנות. אך כל אחד אשר מכיר את המפתח הציבורי יוכל לשלוח אותן ולקבל את הפרטיות הנדרשת.

רעיון אחר אשר נבחן אז היה החלפת מפתחות. כאשר קיימים שני צדדים בתקשורת  יהיה מאד יעיל לייצר מפתח סודי משותף להצפנת מידע רב על ידי שימוש במערכת הצפנה של מפתח סודי. 

ואכן וויטפילד דיפי (Whitfield Diffi) ומרטין הלמן (Martin Hellman) השתמשו בתורת המספרים לבניית נוהל (פרוטוקול) החלפת מפתחות אשר החל את תקופת מערכות ההצפנה של מפתחות ציבוריים. מיד לאחר מכן רון ריוסט (Ron Rivest), עדי שמיר (Adi Shamir) ולאונרד אדלמן (Leonard Adelman) פיתחו מערכת הצפנה אשר הייתה מערכת הצפנה של מפתח ציבורי הראשונה בעלת יכולת הצפנה ויצירת חתימה דיגיטלית (Digital Signature).

מאוחר יותר מספר הופיעו מערכות הצפנה אשר השתמשו  ברעיונות בסיסיים רבים. רבים מהם הוכחו כבלתי בטוחים. מכל מקום תקנון Diffi-Hellman ו- RSA נותרו שתי השיטות החזקות והבטוחות עד עכשיו.

המרכיב הבסיסי בכל מערכת הצפנה של מפתח ציבורי הוא בעיה חישובית קשה. האבטחה של מערכת ההצפנה מבוססת על העובדה שהמפתח הפרטי יכול להיות מחושב מהמפתח הציבורי רק על ידי חישוב הבעיה המסובכת הזו. להלן מספר מונחים הקשורים לשימוש בהצפנה עם מפתח ציבורי.

אלגוריתם הנו תיאור מפורט כיצד תהליך חישובי מסוים צריך להתבצע (או כיצד בעיה צריכה להיפתר).

היעילות של אלגוריתם יכולה להימדד על ידי מספר הפעולות הבסיסיות אשר צריכות להתבצע לפתרון הבעיה. כך שאם נטען שאלגוריתם מתבצע ב- O(n) אזי אנו מתכוונים שהאלגוריתם יתבצע ב- n פעולות בסיסיות, אך איננו מציינים כמה זמן ייקח כל פעולה.