כוח גס

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

חיפוש ממצה

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

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

במקרה הגרוע בעיות NP קשות ניתנות לפתרון רק באמצעות חיפוש ממצה[1], אלא אם כן יתברר ש-P=NP.

התקפת כוח גס בקריפטוגרפיה

התקפת כוח גס קריפטוגרפית ישימה בכמה מישורים כאשר בכולם השיטה בדרך כלל חסרת תחכום ועיקרה הוא ניסוי שיטתי של כל האפשרויות[2].

ניחוש מידע מוצפן

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

ניחוש מפתח הצפנה

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

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

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

ניחוש סיסמה

ניחוש סיסמת משתמש הנקראת גם התקפת מילון היא ניסיון לנחש את סיסמת המשתמש על ידי ניסוי ובדיקה של כל הסיסמאות האפשריות או הסיסמאות הסבירות או הנפוצות ביותר. אם הסיסמה מכילה שמונה תווים מתוך אלפבית בן 36 תווים (26 אותיות ועשר ספרות) והיא אקראית לחלוטין ישנם בסך הכול צירופים אפשריים. גם אם מחשב אחד מסוגל לבדוק מיליון צירופים בשנייה יידרשו 2,821,109 שניות (קצת יותר מחודש) כדי למצוא את הסיסמה הנכונה. ברוב המקרים מערכות אבטחה מציבים מכשולים נוספים כמו הגבלת מספר הניסיונות הכושלים ונעילה של המערכת לפרק זמן ממושך או האטה מכוונת של תהליך הבדיקה עצמו, באופן כזה שלמשתמש הלגיטימי ההאטה תהיה שולית ולא מורגשת ואילו עבור המתקיף היא יוצרת בעיה כיוון שזמן ההתקפה הכולל מתארך עשרת מונים. למעשה במרבית מערכות האבטחה מספר האפשרויות גדול בהרבה. ישנן מערכות שמחייבות הכללה של לפחות סימן פיסוק אחד מתוך 33 אפשריים, בנוסף ל-52 אותיות (רישיות וקטנות) ו-10 ספרות מה שנותן עבור סיסמה בת שמונה סימנים אפשרויות בקירוב.

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


ראו גם

קישורים חיצוניים

  • כוח גס, באתר MathWorld (באנגלית)

Brute Force – המתקפה הכי קלה להסבר, למימוש ולהגנה, בבלוג camelCase

הערות שוליים

  1. ^ Exhaustive Search
  2. ^ Jonathan Katz and Yehuda Lindell (2007). Introduction to Modern Cryptography (2nd edition).
  3. ^ Schneier, Bruce (1996). Applied Cryptography (2nd ed.). John Wiley & Sons. pp. 366–367. ISBN 0-471-11709-9.

Read other articles:

Artikel ini tidak memiliki referensi atau sumber tepercaya sehingga isinya tidak bisa dipastikan. Tolong bantu perbaiki artikel ini dengan menambahkan referensi yang layak. Tulisan tanpa sumber dapat dipertanyakan dan dihapus sewaktu-waktu.Cari sumber: José Maria Neves – berita · surat kabar · buku · cendekiawan · JSTOR José Maria Pereira Neves Perdana Menteri Tanjung VerdeMasa jabatan1 Februari 2001 – 22 April 2016PresidenAntónio Mascare...

 

Johann BayerLahir1572RainMeninggal7 Maret, 1625AugsburgKebangsaanJermanAlmamaterUniversity of IngolstadtDikenal atasUranometriaKarier ilmiahBidangAstronomi Johann Bayer (1572 – 7 Maret, 1625) adalah seorang astronom dan pengacara Jerman. Ia dilahirkan di Rain, Bavaria pada 1572. Ia memulai studi filosofi di Ingolstadt pada 1592, dan kemudian pindah ke Augsburg untuk memulai profesi sebagai pengacara. Di sini ketertarikannya pada astronomi tumbuh. Dia kemudian menjadi penasehat hukum dewan ...

 

Artikel ini bukan mengenai Keong Mas. Keong EmasGenre Drama Remaja Romantis PembuatMD EntertainmentSutradara Sachin Kamlakarhot Didien Rochidien Pemeran Thalita Latief Natasha Dewanti Egi John Foreisythe Yopie Beda Judy Lifa Geccia Moundy Ronald Gustav Penggubah lagu temaChossy PratamaLagu pembukaDenganmu - Sella CRLagu penutupDenganmu - Sella CRNegara asalIndonesiaBahasa asliBahasa IndonesiaJmlh. musim13Jmlh. episode1 (daftar episode)ProduksiProduser eksekutifShania PunjabiProduser Manoj Pun...

هذه مقالة غير مراجعة. ينبغي أن يزال هذا القالب بعد أن يراجعها محرر؛ إذا لزم الأمر فيجب أن توسم المقالة بقوالب الصيانة المناسبة. يمكن أيضاً تقديم طلب لمراجعة المقالة في الصفحة المخصصة لذلك. (ديسمبر 2021) معهد جامعة حجة تبه أنقرة الحكومي معهد جامعة حجة تبه أنقرة الحكومي معهد أنق...

 

NASA satellite of the Explorer program Explorer 8Explorer 8 satelliteNamesS-30NASA-S30Mission typeEarth scienceOperatorNASAHarvard designation1960 Xi 1COSPAR ID1960-014A SATCAT no.00060Mission duration54 days (achieved) Spacecraft propertiesSpacecraftExplorer VIIISpacecraft typeScience ExplorerBusS-30ManufacturerJet Propulsion LaboratoryLaunch mass40.88 kg (90.1 lb)Dimensions76 × 76 cm (30 × 30 in)Power100 watts Start of missionLaunch date3 November 1...

 

العلاقات المكسيكية الباربادوسية المكسيك باربادوس   المكسيك   باربادوس تعديل مصدري - تعديل   العلاقات المكسيكية الباربادوسية هي العلاقات الثنائية التي تجمع بين المكسيك وباربادوس.[1][2][3][4][5] مقارنة بين البلدين هذه مقارنة عامة ومرجعية للدول�...

German field hockey player Tina Bachmann Personal informationBorn (1978-08-01) 1 August 1978 (age 45)Mülheim, North Rhine-Westphalia, West GermanyHeight 1.65 m (5 ft 5 in)Weight 64 kg (141 lb)Playing position DefenderSenior careerYears Team2000–2004 Club Raffelberg2004–2008 Eintracht Braunschweig2008–2009 Laren2009–2014 Oranje ZwartNational teamYears Team Apps (Gls)2000–2014 Germany 255 Medal record Women's field hockey Representing  Germany Olymp...

 

Canadian ice hockey player Ice hockey player Erin Ambrose Ambrose with PWHL Montreal in 2024Born (1994-04-30) April 30, 1994 (age 29)Keswick, Ontario, CanadaHeight 5 ft 5 in (165 cm)Weight 132 lb (60 kg; 9 st 6 lb)Position DefenceShoots RightPWHL teamFormer teams PWHL MontrealLes Canadiennes de MontréalClarkson Golden KnightsToronto FuriesNational team  CanadaPlaying career 2012–present Medal record Women's ice hockey Representing  Cana...

 

U.S. House district for Tennessee TN-9 redirects here. The term may also refer to Tennessee State Route 9. Tennessee's 9th congressional districtInteractive map of district boundaries since January 3, 2023Representative  Steve CohenD–MemphisDistribution98.54% urban[1]1.46% ruralPopulation (2022)756,975[2]Median householdincome$53,183[3]Ethnicity60.2% Black25.2% White9.2% Hispanic2.8% Two or more races2.0% Asian0.6% otherCook PVID+22[4] Tennessee's 9th co...

Soumont-Saint-QuentincomuneSoumont-Saint-Quentin – Veduta LocalizzazioneStato Francia Regione Normandia Dipartimento Calvados ArrondissementCaen CantoneFalaise TerritorioCoordinate48°59′N 0°14′W / 48.983333°N 0.233333°W48.983333; -0.233333 (Soumont-Saint-Quentin)Coordinate: 48°59′N 0°14′W / 48.983333°N 0.233333°W48.983333; -0.233333 (Soumont-Saint-Quentin) Superficie6,88 km² Abitanti586[1] (2009) Densità85,17 a...

 

Disambiguazione – Se stai cercando altri significati, vedi Stephen Foster (disambigua). Stephen Collins Foster Stephen Collins Foster (Pittsburgh, 4 luglio 1826 – New York, 13 gennaio 1864) è stato un compositore statunitense. Conosciuto come il padre della musica americana, fu il più noto compositore e scrittore di canzoni del XIX secolo negli Stati Uniti. Le sue canzoni, fra cui la celeberrima Oh! Susanna, rimangono conosciute e popolari in tutto il mondo dopo più di un secolo e mez...

 

1968 studio album by Wes MontgomeryWillow Weep for MeStudio album by Wes MontgomeryReleasedDecember 1968[1]Recorded1965GenreJazzLabelVerveProducerEsmond EdwardsWes Montgomery chronology Road Song(1968) Willow Weep for Me(1968) Willow Weep for Me is a posthumous jazz album recorded by guitarist Wes Montgomery in 1965 and released in 1968. It reached number 12 on the Billboard Jazz album chart in 1969. At the Grammy Awards of 1970 Willow Weep for Me won the Grammy Award for Best...

Municipal building in Reading, Berkshire, England Reading Town HallThe town hall in 2018Location within Reading Town CentreGeneral informationTypeTown hallArchitectural styleItalianateClassification Listed Building – Grade II*Designated22 March 1957Reference no.1113400 LocationReading, Berkshire, UKCoordinates51°27′25″N 0°58′12″W / 51.45695°N 0.97005°W / 51.45695; -0.97005Construction started1786Completed1875; 149 years ago (1875)De...

 

Philosophical paradox regarding free will Political cartoon c. 1900, showing the United States Congress as Buridan's ass (in the two hay piles version), hesitating between a Panama route or a Nicaragua route for an Atlantic–Pacific canal. Buridan's ass is an illustration of a paradox in philosophy in the conception of free will. It refers to a hypothetical situation wherein an ass (donkey) that is equally hungry and thirsty is placed precisely midway between a stack of hay and a pail o...

 

此条目序言章节没有充分总结全文内容要点。 (2019年3月21日)请考虑扩充序言,清晰概述条目所有重點。请在条目的讨论页讨论此问题。 哈萨克斯坦總統哈薩克總統旗現任Қасым-Жомарт Кемелұлы Тоқаев卡瑟姆若马尔特·托卡耶夫自2019年3月20日在任任期7年首任努尔苏丹·纳扎尔巴耶夫设立1990年4月24日(哈薩克蘇維埃社會主義共和國總統) 哈萨克斯坦 哈萨克斯坦政府...

Стаття є частиною циклу просхоластику Джерела Біблія | Євангеліє Античні учені: Аристотель | Евклід | Птолемей | Платон Отці Церкви: Августин Аврелій | Діонісій Ареопагіт | Іван Дамаскін | Боецій Течії Томізм | Скотизм | Концептуалізм | Номіналізм | Реалізм | Августинізм | Аве...

 

Function of federal and other governments Main article: Energy law United States energy law is a function of the federal government, states, and local governments. At the federal level, it is regulated extensively through the United States Department of Energy. Every state, the federal government, and the District of Columbia collect some motor vehicle excise taxes.[1] Specifically, these are excise taxes on gasoline, diesel fuel, and gasohol.[1] While many western states rely...

 

Racial term De Mestizo y de India; Coyote. Miguel Cabrera, 1763, oil on canvas, Waldo-Dentzel Art Center. De mestizo e india, sale coiote. Anonymous, 18th century (From a Mestizo man and an Amerindian woman, a coyote is begotten). De Castizo y India, Coyota. Anonymous, 18th century Mexico. Coyote (fem. Coyota) (from the Nahuatl word coyotl, coyote) is a colonial Spanish American racial term for a mixed-race person casta that usually refers to a person born of parents, one of whom a Mestizo (m...

UK-based media company UBM redirects here. For other uses, see UBM (disambiguation). UBM plcCompany typePublic limited companyISINJE00BD9WR069 IndustryMediaFounded1918; 106 years ago (1918)FounderDavid Lloyd GeorgeDefunct2018; 6 years ago (2018)FateAcquired by InformaHeadquartersLondon, England, UKKey peopleGreg Lock (Acting Chairman)Tim Cobbold (CEO)ProductsExhibitionsMarketing servicesRevenue£1,002.9 million (2017)[1]Operating income£229.1 ...

 

هذه المقالة يتيمة إذ تصل إليها مقالات أخرى قليلة جدًا. فضلًا، ساعد بإضافة وصلة إليها في مقالات متعلقة بها. (نوفمبر 2021) لا تتدخل فيما لا يعنيك هو مثل انجليزي شائع والذي يعني احترام خصوصية الآخرين، ويُلزَم على الشخص حال سماعه التوقف عن التدخل في شؤون ليست لهم أو لا تعنيهم، وسي�...