הצגת המקור של הדף "כוח גס"

ב[[מדעי המחשב]], [[מתמטיקה]] ו[[קריפטוגרפיה]], '''כוח גס''' או '''תְּקִיפָה כּוֹחָנִית''' (לפי [[האקדמיה ללשון העברית]]) מאנגלית: Brute force, או '''חיפוש ממצה''' מאנגלית: Exhaustive search, מתייחס לתהליך או [[אלגוריתם]] שפועל באופן של [[ניסוי וטעייה]] של כל האפשרויות לפתרון בעיה נתונה עד למציאת הפתרון הנכון. מקור הביטוי בעובדה שבדרך כלל שיטה ישירה שאינה מנצלת קיצורי דרך אינטליגנטיים, דורשת הפעלת כוח לא מידתי או השקעת אנרגיה רבה בתקווה שהפתרון יימצא בסופו של דבר ולכן איננה נחשבת יעילה.

==חיפוש ממצה==
במדעי המחשב חיפוש ממצה מתאר טכניקות גנריות לפתרון בעיות מתמטיות המסתמכות על מיפוי שיטתי של כל הפתרונות האפשריים ובדיקה האם נמצא ביניהם פתרון לבעיה נתונה. לדוגמה [[פירוק לגורמים של מספר שלם|אלגוריתם פירוק לגורמים של מספרים שלמים]] בשיטת [[חילוק ניסיוני]] (trial division) או מציאת [[מסלול המילטוני]] ב[[גרף (תורת הגרפים)|גרף]]. בדרך כלל אלגוריתם חיפוש ממצה פשוט וקל ליישום ובסופו מובטח שיימצא הפתרון אם קיים, לכן שיטות כוח גס יכולות להיות שימושיות כאשר טווח החיפוש קטן, או כאשר קיימת [[היוריסטיקה]] המאפשרת לצמצם את טווח החיפוש לכדי גודל בר ביצוע כמו [[התקפת איזון זמן/זיכרון|איזון זמן/זיכרון]]. או כאשר יש עדיפות לשיטות פשוטות וקלות ליישום על פני מהירות ביצוע. אלגוריתם כוח גס יכול לשמש גם כאלגוריתם ייחוס לצורך השוואת ביצועים.

המושג "'''כוח גס'''" תקף גם ל[[הוכחה|הוכחות מתמטיות]] שבהן השיטה להוכחה היא ביצוע חישובים ארוכים ומייגעים, אך ישירים, של כל המקרים האפשריים, במקום לחשוב על פתרון אלגנטי יותר. ההוכחה הראשונה של [[בעיית ארבעת הצבעים|משפט ארבעת הצבעים]] מורכבת משני צעדים: ראשית מראים שכדי להוכיח את הטענה (המתייחסת לאינסוף מצבים), מספיק לבדוק אותה ב-1,936 מקרים מסוימים; אלו נבדקים ב'כוח', ב[[מחשב]].

במקרה הגרוע [[NP (מחלקת סיבוכיות)|בעיות NP קשות]] ניתנות לפתרון רק באמצעות חיפוש ממצה{{הערה|[http://mathworld.wolfram.com/ExhaustiveSearch.html Exhaustive Search]}}, אלא אם כן יתברר ש-[[P=NP]].

==התקפת כוח גס בקריפטוגרפיה==
התקפת כוח גס קריפטוגרפית ישימה בכמה מישורים כאשר בכולם השיטה בדרך כלל חסרת תחכום ועיקרה הוא ניסוי שיטתי של כל האפשרויות{{הערה|Jonathan Katz and Yehuda Lindell (2007). [http://www.cs.umd.edu/~jkatz/imc.html Introduction to Modern Cryptography (2nd edition)].}}.

====ניחוש מידע מוצפן====
מהיבט של [[תורת האינפורמציה]] [[סודיות מושלמת|צופן מושלם]] הוא צופן כזה שלא משנה כמה עוצמת מחשוב זמינה בידי המתקיף, הוא לעולם לא יצליח לפענח את הטקסט המוצפן כי פשוט אין בידיו המידע המינימלי הדרוש כדי לפענחו. במילים אחרות הניסיון לנחש את הטקסט הגלוי נותן מספר אפשרויות כל כך גדול שאין בו כל תועלת. אולם ביטחון מושלם אינו בר השגה מבחינה מעשית ולכן בפועל מתפשרים על ביטחון חישובי לפיו ביטחון האלגוריתם נמדד במונחים של הזמן הדרוש כדי לפצח אותו. בהנחה שלא קיימת דרך קצרה אלא הדרך היחידה לפרוץ את האלגוריתם היא באמצעות ניסוי כל המפתחות האפשריים כדי לגלות את המפתח בו השתמש המצפין, הרי שבעצם [[סיבוכיות]] ההתקפה נגד האלגוריתם נמדדת לפי אורך המפתח בסיביות ככל שהוא ארוך יותר כך סיבוכיות ההתקפה עולה באופן מעריכי. אילו מפתח ההצפנה היה כאורך המסר עצמו והוא נבחר באקראי מספר האפשרויות במקרה זה היה מקסימלי כמו ב[[פנקס חד-פעמי]] כאמור, אולם במערכת הצפנה מודרנית בפועל מפתח ההצפנה קטן מאוד בהשוואה לטקסט המוצפן בניסוח פורמלי <math>|\mathcal{K}|<|\mathcal{M}|</math>, עובדה זו מדליפה מעט מידע שיכול לשמש את המתקיף, כי בהינתן טקסט מוצפן <math>c</math> המתקיף יכול לנסות לפענחו עם כל המפתחות האפשריים <math>k\in\mathcal{K}</math> ולקבל רשימה של כל הטקסטים הגלויים האפשריים. הרשימה אינה יכולה להכיל את כל המרחב <math>\mathcal{M}</math> כיוון שמרחב המפתח עצמו קטן יותר ולכן הוא יכול לנחש את המפתח הנכון מתוך רשימת המפתחות האפשריים ולהצליח בהסתברות שהיא טובה יותר מההסתברות במקרה של פנקס חד-פעמי. יתרה מזו, אם נניח שהיריב הצליח לגלות מעט טקסט מוצפן מבלי לנחש את המפתח (ייתכן שהוא השיג זאת בדרך אחרת כמו על ידי [[ציתות]] וגנבה) וכעת בידיו מספר זוגות של טקסטים מוצפנים <math>c_1,...,c_{\ell}</math> וגלויים <math>m_1,...,m_{\ell}</math> כך שמתקיים <math>c_i=\text{Enc}_k(m_i)</math> עבור כל הטקסטים מ-1 עד <math>\ell</math>. הוא יכול לנסות לפענח כל אחד מהטקסטים המוצפנים שבידו עם כל המפתחות האפשריים עד שנמצאת התאמה, כלומר שמתקיים <math>m_i=\text{Dec}_k(c_i)</math> עבור כל <math>i</math> מ-1 עד <math>\ell</math>. המפתח שיימצא יהיה ייחודי ולמעשה יהיה מפתח ה[[הצפנה]] שאיתו השתמש המצפין בהסתברות גבוהה, איתו הוא יכול לפענח את יתרת הטקסט המוצפן.

====ניחוש מפתח הצפנה====
ניחוש [[מפתח (קריפטוגרפיה)|מפתח הצפנה]]{{הערה|Schneier, Bruce (1996). Applied Cryptography (2nd ed.). John Wiley & Sons. pp. 366–367. {{ISBN|0-471-11709-9}}.}} הוא ניסיון לפענח טקסט מוצפן נתון באמצעות כל המפתחות האפשריים ולבדוק האם התוצאה מתאימה לטקסט גלוי מסוים. אם נמצאת התאמה המפתח שהתגלה יכול לשמש כדי לפענח את כל המסרים שהוצפנו או יוצפנו עם מפתח זה. מהיבט מעשי, בניגוד ל[[פנקס חד-פעמי]] שבו המפתח כאורך הטקסט המוצפן, השאיפה היא שיהיה אפשר להצפין מסרים ארוכים עם מפתח קצר. במצב כזה ביטחון ניתן להשגה אך ורק אם מגבילים את יכולת היריב לשבור את הצופן. או לחלופין מגבילים את [[זמן ריצה (תוכנה)|זמן הריצה]] שלו כך שלא יהיה לו מספיק זמן כדי להשלים את ההתקפה בכוח גס. למעשה מאפשרים מצב שהיריב יוכל בהסתברות מאוד מאוד נמוכה לשבור את הצופן. התקפה מסוג זה היא ליניארית ביחס ל-<math>|\mathcal{K}|</math> וסיבוכיותה מעריכית, ככל שהמפתח גדול יותר מספר האפשרויות גדל באופן מעריכי.

לדוגמה נניח שברשות המתקיף [[מחשב על]] שמסוגל לבצע מיליון הצפנות בשנייה, אם המפתח באורך 56 סיביות כמו במקרה של [[DES]] יידרשו 2,285 שנים כדי למצוא את המפתח הנכון. לפני כשני עשורים הייתה הערכה שאם יהיה אפשר לבנות מכונה ייעודית המכילה כמיליון שבבים שיכולים לבצע באופן [[חישוב מקבילי|מקבילי]] כמיליון הצפנות בשנייה אז ניתן יהיה לשבור את DES בכוח גס בזמן של 20 שעות לכל היותר, לעומת זאת אם המפתח באורך 64 סיביות יידרשו 214 ימים. בשנים האחרונות חלה התפתחות טכנולוגית כך שבמחיר של פחות ממיליון דולר אפשר לבנות מכונה לפיצוח DES שתמצא את המפתח בתוך מספר שעות. לפי [[חוק מור]] ההערכה הכללית הייתה שכוח המחשוב יוכפל אחת לשמונה עשר חודשים, ואכן כיום קיימים בשוק שבבים ייעודיים שמסוגלים לשבור את DES בזמן מאוד קצר ובעלות נמוכה בהרבה. זו למעשה הסיבה העיקרית מדוע DES הוחלף ב-AES.

אם המפתח באורך 128 סיביות מספר האפשרויות לניחושו הוא <math>2^{128}</math> שזה מספר אסטרונומי, מספר השנים שיעברו עד שהמתקיף ימצא את המפתח הנכון הוא <math>10^{25}</math> שנים שזה גדול בהרבה מגיל היקום. ההערכה נכון לשנת 2017 היא שמפתח באורך 128 סיביות נמצא מחוץ להישג יד וחיפוש ממצה של המפתח בכוח גס אפילו בהפעלה מקבילית של מיליוני מחשבי על, אינו מעשי כלל. כמובן שיש להביא בחשבון שבכל רגע עלולה להתגלות דרך מתוחכמת יעילה יותר מכוח גס לשבירת אלגוריתם ההצפנה. מפתחי אלגוריתמים שואפים להגיע למצב שאלגוריתם ההצפנה שפיתחו יהיה ניתן לשבירה אך ורק באמצעות כוח גס כי אז אפשר לשלוט בביטחון האלגוריתם על ידי קביעת אורך מפתח הצפנה באופן כזה שהתקפת כוח גס תהיה מחוץ להישג יד.

====ניחוש סיסמה====
ניחוש [[סיסמה|סיסמת משתמש]] הנקראת גם [[התקפת מילון]] היא ניסיון לנחש את סיסמת המשתמש על ידי ניסוי ובדיקה של כל הסיסמאות האפשריות או הסיסמאות הסבירות או הנפוצות ביותר. אם הסיסמה מכילה שמונה תווים מתוך [[אלפבית]] בן 36 תווים (26 אותיות ועשר ספרות) והיא אקראית לחלוטין ישנם בסך הכול <math>36^{8}\approx 10^{13}</math> צירופים אפשריים. גם אם מחשב אחד מסוגל לבדוק מיליון צירופים בשנייה יידרשו 2,821,109 שניות (קצת יותר מחודש) כדי למצוא את הסיסמה הנכונה. ברוב המקרים מערכות אבטחה מציבים מכשולים נוספים כמו הגבלת מספר הניסיונות הכושלים ונעילה של המערכת לפרק זמן ממושך או האטה מכוונת של תהליך הבדיקה עצמו, באופן כזה שלמשתמש הלגיטימי ההאטה תהיה שולית ולא מורגשת ואילו עבור המתקיף היא יוצרת בעיה כיוון שזמן ההתקפה הכולל מתארך עשרת מונים. למעשה במרבית מערכות האבטחה מספר האפשרויות גדול בהרבה. ישנן מערכות שמחייבות הכללה של לפחות סימן [[פיסוק]] אחד מתוך 33 אפשריים, בנוסף ל-52 אותיות (רישיות וקטנות) ו-10 ספרות מה שנותן עבור סיסמה בת שמונה סימנים <math>95^{8}\approx 10^{16}</math> אפשרויות בקירוב.

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

<!--
ב[[מדעי המחשב]], '''כוח גס''' (או: '''כוח ברוטלי''', מאנגלית: '''Brute Force''') הוא סוג של [[אלגוריתם]] שאין בו תחכום, כזה הפועל בדרך הפשוטה ביותר להשגת המטרה, תוך שהוא צורך לעיתים כמויות גדולות יחסית של משאבי מחשב (זמן או [[זיכרון מחשב|זיכרון]]).

דוגמה לאלגוריתם מסוג זה הוא פיצוחן של [[סיסמה|סיסמאות]] כניסה למחשב באמצעות ניסיון להיכנס עם כל הסיסמאות האפשריות, עד להצלחה. טכניקה זו אינה יעילה, בדרך-כלל, מכיוון שמספר הצירופים האפשריים הוא עצום. לסיסמה בת 8 תווים עם [[אלפבית]] בן 36 סוגי תווים ישנם 2,821,109,907,456 = 36<sup>8</sup> אפשרויות שונות. נניח שישנה אפשרות לנסות מיליון סיסמאות בשנייה, במצב הזה יקח לנסות את כלל האפשריות 2,821,109 שניות שהן קצת יותר מחודש. במקרה זה אלגוריתם הפועל בכוח גס אינו מצליח לתת פתרון נאות לבעיה (למעשה במקרים רבים תינעל האפשרות להזדהות כבר לאחר ניסיונות מעטים, ואם אין נעילה אזי תיוצר השהיה מכוונת בין ניסיונות עוקבים).

בשנים הראשונות לפיתוחה של [[תוכנת שחמט]] נגד אדם, היה הפתרון של כוח גס מקובל למדי: עוצמת החישוב העצומה של המחשב נוצלה לשם בדיקת כל המהלכים האפשריים צעדים אחדים קדימה. התוכנה הצליחה להתמודד עם האדם, אך גם כאן ניכרה חולשתו של הכוח הגס: נדרשה עוצמה של [[מחשב-על]] כדי להתמודד עם שחקן טוב. בהמשך פיתוחן של תוכנות השחמט הוחלפה גישת הכוח הגס באלגוריתמים מתוחכמים יותר, המאפשרים גם ל[[מחשב אישי]] להתמודד עם אלוף העולם.

 -->

==ראו גם==
* [[קריפטואנליזה]]
* [[התקפת איזון זמן/זיכרון]]

== קישורים חיצוניים ==
* {{MathWorld}}

[https://camelcase.blog/brute-force-rate-limit/ Brute Force – המתקפה הכי קלה להסבר, למימוש ולהגנה], בבלוג camelCase

==הערות שוליים==
{{הערות שוליים|יישור=שמאל}}

{{קריפטוגרפיה|קריפטואנליזה}}
[[קטגוריה:אלגוריתמים]]
[[קטגוריה:שיטות הוכחה]]
[[קטגוריה:תקיפות קריפטוגרפיות]]
[[קטגוריה:הוכחה באמצעות מחשב]]